兑换零钱(一)

import java.util.*;


public class Solution {
    public int minMoney (int[] arr, int aim) {
        int[] dp = new int[aim+1];  // dp数组记录每一个目标金额，对应的最小找零数
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= aim; i++) {
            for (int money : arr) {
                if (i >= money && dp[i-money] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i-money]+1, dp[i]);
                }
            }
        }

        return dp[aim] == Integer.MAX_VALUE ? -1 : dp[aim];
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public int minMoney (int[] arr, int aim) {
        // write code here

        // 算法核心：动态规划（由于状态转移是基于for循环的，因此记忆化搜索不能够与动态规划相媲美了）

        // 先处理特殊值
        if (aim == 0) {
            return 0;
        }
        if (arr.length == 0) {
            return -1;
        }
        // dp[i][j] - 考虑第i个及以后的币种，目标是凑齐j，所需要的最少货币数
        // 先统一初始化成Integer.MAX_VALUE
        int[][] dp = new int[arr.length + 1][aim + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }

        // 初始化：对于[arr.length][0]   - 钱用完了，且刚好余额为0，不需要兑换了    -> 0
        //            [arr.length][>0]  - 钱用完了，但余额还有剩余，这种兑法是错的 -> Integer.MAX_VALUE表示错误
        //            [][0]             - 钱没用完，但是余额已经正好为0，兑换结束  -> 0
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }
        // 状态转移方程：考虑当前币值用n(0 ~ j/arr[i])次 - dp[i][j] = Math.min(n + dp[i + 1][j - n*arr[i]])
        // i - 从下（大）往上（小）推
        // j - 从左（小）往右（大）推
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 1; j < dp[0].length; j++) {
                int n = j / arr[i];
                int min = Integer.MAX_VALUE;
                for (int k = 0; k <= n; k++) {
                    int cur = dp[i + 1][j - k * arr[i]];
                    if (cur != Integer.MAX_VALUE) {
                        cur += k;
                    }
                    if (cur < min) {
                        min = cur;
                    }
                }
                dp[i][j] = min;
            }
        }
        // int result =  process(arr, 0, aim);
        int result = dp[0][aim];
        if (result == Integer.MAX_VALUE) {
            return -1;
        } else {
            return result;
        }
    }


    // 如果对递归方程没思路，可将以下【递归回溯】改写成【动态规划】:
    //      1.递归出口 -> 初始化条件
    //      2.递归分支 -> 状态转移方程

    // public int process (int[] arr, int i, int j) {
    //     // 递归出口
    //     if (i == arr.length) {
    //         if (j == 0) {
    //             // 刚好到达j，算作是一个货币数目
    //             return 0;
    //         } else {
    //             // 无效情况
    //             return Integer.MAX_VALUE;
    //         }
    //     }
    //     if (j == 0) {
    //         return 0;
    //     }

    //     // 递归分支
    //     // 考虑当前币种用几张
    //     int min = Integer.MAX_VALUE;
    //     for (int m = 0; m <= j / arr[i]; m++) {
    //         // 本币值用m张
    //         // 后续情况
    //         int next = Math.min(Integer.MAX_VALUE, process(arr, i + 1, j - m * arr[i]));
    //         // 检验有效性，加上本货币使用个数
    //         int cur = Integer.MAX_VALUE;
    //         if (next != Integer.MAX_VALUE) {
    //             // 有效
    //             cur = next + m;
    //         }
    //         if (cur < min) {
    //             min = cur;
    //         }
    //     }

    //     return min;
    // }
}

public int minMoney (int[] arr, int aim) {
    // write code here
    int[] dp=new int[aim+1];
    Arrays.fill(dp ,aim+1);
    dp[0]=0;
    for(int i=1;i<=aim;i++){
        for(int j=0;j<arr.length;j++){
            if(arr[j]<=i){
                // 如果存在面值不大于当前零钱的面值，那么dp[零钱]=dp[零钱-面值]+1
                dp[i]=Math.min(dp[i] ,dp[i-arr[i]]+1);
            }
        }
    }
    return dp[aim]<=aim?dp[aim]:-1;
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    // 思路：将要找的钱数aim看作背包容量，将货币面值看作石头重量，求将容量为aim的背包装满
    // 的最少货币数
    public int minMoney (int[] arr, int aim) {
        // write code here
        // dp[i]表示组成要找的钱数i时的最少货币数
        int[] dp = new int[aim + 1];
        // 要找的钱数为0时，最少的货币数为0，所以初始化dp[0]=0
        dp[0] = 0;
        int max = Integer.MAX_VALUE;
        // 将要找钱数1~aim对应的最少货币数初始化为int的最大值，防止在递推过程中Math.min时
        // 取到错误值
        for (int k = 1; k < aim + 1; k++) {
            dp[k] = max;
        }
        // 遍历，在组合中添加将面值arr[i]的货币，使得组合总额==要找的钱数，用dp[j]记录最少
        // 货币数
        for (int i = 0; i < arr.length; i++) {
            for (int j = arr[i]; j <= aim; j++) {
                // dp[j - arr[i]] == max表示dp[j - arr[i]]对应要找的钱数！=组合的钱数总额
                // 此时在往组合中添加货币arr[i]也不能使得新的组合钱数总额=要找的钱数
                if (dp[j - arr[i]] != max) {
                    // 递推公式：比较上一轮i循环得到的最少货币数组合dp[j]和当前循环得到的j
                    // 的最少货币数组合dp[j - arr[i]] + 1，取较小值。dp[j - arr[i]]表示
                    // 要找钱数j-arr[i]的最少货币组合，j - arr[i]+arr[i]=j,即往dp[j - arr[i]]
                    // 对应的组合中加入货币arr[i]后，组合的货币总额等于要找的钱数j，新增了1个货币
                    // arr[i],所以此时的dp[j]=dp[j - arr[i]] + 1
                    dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);
                }
            }
        }
        if (dp[aim] == max) return -1;
        else return dp[aim];
    }
}

public int minMoney (int[] arr, int aim) {
        int[] dp=new int[aim+1];
        Arrays.fill(dp,aim+3);
        dp[0]=0;//当容量为0，装0个物品
        for(int i=0;i<arr.length;i++){
            for(int j=arr[i];j<aim+1;j++){
                dp[j]=Math.min(dp[j],dp[j-arr[i]]+1);
            }
        }
        if(dp[aim]==aim+3){
            return -1;
        }
        return dp[aim];

    }

public class Solution {
    public int minMoney (int[] arr, int aim) {
        // 凑成i块钱所需要的最少货币数
        int[] dp = new int[aim + 1];
        Arrays.fill(dp, aim + 1);
        // 凑成0元需要0个货币数
        dp[0] = 0;
        // 先遍历货币
        for (int c : arr) {
            // 后根据货币数值遍历目标金额
            for (int i = c; i <= aim; i++) {
                // 将当前货币加入
                // 不将当前货币加入
                // 取个最小值
                dp[i] = Math.min(dp[i - c] + 1, dp[i]);
            }
        }
        // 如果目标金额的所需最少货币数是aim+1，说明凑不成aim
        return dp[aim] == aim + 1 ? -1 : dp[aim];
    }
}

public class Solution {
    public int minMoney (int[] arr, int aim) {
        // 凑成i块钱所需要的最少货币数
        int[] dp = new int[aim + 1];
        Arrays.fill(dp, aim + 1);
        // 凑成0元需要0个货币数
        dp[0] = 0;
        // 先遍历目标金额
        for (int i = 1; i <= aim; i++) {
            // 遍历货币
            for (int c : arr) {
                // 如果目标金额比货币值还小，直接跳过
                if (i < c) {
                    continue;
                }
                // 将当前货币加入
                // 不将当前货币加入
                // 取个最小值
                dp[i] = Math.min(dp[i - c] + 1, dp[i]);
            }
        }
        // 如果目标金额的所需最少货币数是aim+1，说明凑不成aim
        return dp[aim] == aim + 1 ? -1 : dp[aim];
    }
}

import java.util.*;


public class Solution {

    public int minMoney (int[] arr, int aim) {
        // write code here
        int maxNum = aim + 1; //边界条件
        int[] dp = new int[aim + 1];//凑齐零钱的最小硬币数
        Arrays.fill(dp, maxNum); //初始化
        dp[0] = 0;//零元零种
        for (int i = 0; i < arr.length; i++) { //每种硬币
            for (int j = arr[i]; j <= aim; j++) { //总零钱数
                dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);//1个硬币 + 凑齐（总零钱 - 单个硬币的面值）的最小硬币数
            }
        }
        return dp[aim] == maxNum ? -1 : dp[aim];
    }
}

public int minMoney (int[] arr, int aim) {
    // dp[x]表示组成x的最小货币数
    int[] dp = new int[aim + 1];
    for (int i = 1; i < aim + 1; i++) {
        // 不同纸币组合
        List<Integer> list = new ArrayList<>();
        for (int a : arr) {
            if (i - a >= 0 && dp[i - a] != -1) {
                list.add(dp[i - a]);
            }
        }
        // 组合为空，说明不存在兑换
        if (list.isEmpty()) {
            dp[i] = -1;
        } else {
            // 取组合中数量最少的，加上1
            dp[i] = Collections.min(list) + 1;
        }
    }
    return dp[aim];
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public int minMoney (int[] arr, int aim) {
        // write code here
        if(aim == 0){
            return 0;
        }
        // 思路：每一个dp[i]都代表该dp[i]能否被找零，arr数组里面的数，代表dp[数]一定是能被找零的，接下来往后推即可
        int dp[] = new int[aim+1];
        Arrays.fill(dp,1,dp.length,aim+1);
        for(int i=1; i<=aim; i++){
            for(int coin : arr){
                if(i-coin < 0 || dp[i-coin]>=aim) continue;
                dp[i] = Math.min(dp[i-coin]+1,dp[i]);
            }
        }
        return dp[aim] == aim +1  ? -1 : dp[aim];
    }
}

import java.util.*;
public class Solution {
    public int minMoney (int[] arr, int aim) {
        int n = arr.length;
        int[] dp = new int[aim+1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        
        for(int i=0; i<=aim; i++){
            int res = Integer.MAX_VALUE;
            for(int j=0; j<n; j++){
                int num = i-arr[j];
                if(num >=0 && dp[num]!=-1){
                    res = Math.min(res, dp[num] + 1);
                }
            }
            if(res!=Integer.MAX_VALUE) dp[i] = res;
        }
        return dp[aim];
    }
}

import java.util.*;

public class Solution {
    public int minMoney (int[] arr, int aim) {
        //dp[i]表示凑成金额i的最少货币数
        int[] dp = new int[aim + 1];
        //初始化化dp数组为aim+1,方便后面取最小值
        Arrays.fill(dp, aim + 1);
        //金额为0，则货币数为0
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            for (int coin : arr) {
                //金额大于币值才能凑
                 if (i >= coin) {
                     dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                 }
            }
        }
        //如果dp[amount]还是最大值，则返回-1
        return dp[aim] == aim + 1 ? -1 : dp[aim];
    }
}

动态规划： DP方程很重要，只要能推到出DP方程，这道题就OK

import java.util.*;
public class Solution {
    /**
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public int minMoney (int[] arr, int aim) {
        // 定义DP方程
        int[] dp = new int[aim + 1];
        // 初始化为最大值
        Arrays.fill(dp, aim + 1);
        // 当aim为0时，表示不需要换钱
        dp[0] = 0;
        // [1,2,4],DP方程转移状态
        for (int i = 1; i <= aim; i++) {
            for (int j = 0; j < arr.length; j++) {
                // 是否可兑换，当前的货币 < 钱币
                if (arr[j] <= i) {
                    // 当前钱币 = 没兑换前的 + 1
                    dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);
                }
            }
        }
        return dp[aim] > aim ? -1 : dp[aim];
    }
}

public class Solution {
    /**
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     动态规划公式：
     dp[i]=min(dp[i-arr[0]]+1,dp[i-arr[1]]+1.....)
     以[5,2,3],20为例子
     dp[20]的值就是凑出20所需要的最少硬币的值
     dp[20]的可能性：dp[15]+1(面值为5的硬币)；dp[18]+1(面值为2的硬币)；dp[17]+1(面值为3的硬币)
     dp[15]的可能性：dp[10]+1(面值为5的硬币)；dp[13]+1(面值为2的硬币)；dp[12]+1(面值为3的硬币)
     */
    public int minMoney (int[] arr, int aim) {
        // write code here
        int[] dp = new int[aim+1];
        int MAX=aim+1;//设置最大值为目标金额+1
        Arrays.fill(dp,MAX);//因为要求最小值，所以把dp数组全部定义为最大值
        dp[0]=0;
        for(int i = 1;i<=aim;i++){//求出凑出1-aim元的最少硬币数目
            for(int j=0;j<arr.length;j++){//遍历硬币面额
                if(i-arr[j]<0){//如果出现类似于dp[5]=dp[-4]+1的情况则不予考虑
                    continue;
                }
                dp[i]=Math.min(dp[i],dp[i-arr[j]]+1);//在现在的dp值与新计算的dp可能取更小值
            }
        }
        return dp[aim]>aim?-1:dp[aim];//最后将dp[aim]与aim作比较，如果它还是最大值MAX则输出-1
    }
}

import java.util.*;
public class Solution {
    public int minMoney(int[] arr, int aim)
    {
        int[] dp = new int[aim + 1];
        // dp[0] 为 0，其他默认为 amount + 1（实际是不可能的），为了方便取对比结果中的最小值
        Arrays.fill(dp,aim+1);
        dp[0]=0;
        // 计算 1~aim 每项 dp[i] 的值
        for (int i = 1; i <= aim; i++)
        {
            for (int j = 0; j < arr.length; j++)
            {
                // 如果i能使用存在的面额来组合，得到每种面值组合后的最小值
                if (arr[j] <= i)
                {
                    dp[i] = Math.min(dp[i], dp[i-arr[j]] + 1);
                }
            }
        }
      // 如果dp[aim]是aim+1，代表没找到组合结果，否则返回组合成aim需要的最少硬币数:dp[aim]
      return dp[aim] > aim ? -1 : dp[aim];
    }
}

import java.util.*;


public class Solution {
    /**
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public int minMoney (int[] arr, int aim) {
        // write code here
        // write code here
        //完全背包 组合数
        //先物品 再背包（从小到大）
        //dp[i] 组成i的包 用的最少货币数
        if(arr.length==0){
            return -1;
        }
        if (aim == 0)return 0;
        int[] dp = new int[aim+1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 5001;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int bagweight = arr[i]; bagweight <= aim ; bagweight++) {
                dp[arr[i]] = 1;
                dp[bagweight] = Math.min(dp[bagweight],dp[bagweight-arr[i]]+1);
            }
        }
        if (dp[aim] == 5001){
            return -1;
        }else {
            return dp[aim];
        }
    }
}

    // 确定状态转移方程：f(x) = min{f(x-arr[0])+1, f(x-arr[1])+1)...}
    public int minMoney (int[] arr, int aim) {
        int[] f = new int[aim + 1]; // 记录状态数组
        Arrays.fill(f, aim + 1);
        f[0] = 0; // 初始条件
        for (int i = 1; i <= aim; i++) {
           for (int j = 0; j < arr.length; j++) {
                if (i-arr[j] >= 0) // 边界条件判断
                    f[i] = Math.min(f[i], f[i - arr[j]] + 1);
            }
        }
        return f[aim]==aim + 1 ? -1 : f[aim];
    }
}