题目

image.png

思路

  • 零钱兑换属于01背包类问题，01背包问题：当前考虑的物品拿或者不拿
  • 完全背包问题：当前考虑的物品拿或者不拿，如果拿，只要背包能装下，就可以一直拿，直到背包装不下为止。
  • 思路一：暴力递归，每次递归时由两个分支选择这个硬币还是不选择这个硬币，当前硬币面值小于才选择该硬币，最后筛选所有硬币所需个数最小的那种
  • 思路二：备忘录，使用容器记录重复递归问题

  • 思路三：动态规划，定义dp[i]表示当前待兑换金额i所需的最小硬币个数，dp[i]依赖于dp[i-coin] + 1和dp[i]的最小和，意思就是待兑换金额i，当使用硬币coin时，此时硬币数加1，剩余待兑换金额为i-coin，如果dp[i-coin]是最小的个数，自然dp[i]也是最小的

    代码

    1.   //1.暴力递归超时
    2.   public int coinChange(int[] coins, int amount) {
    3.       if (amount < 0) return -1;
    4.       if (amount == 0) return 0;
    5.       int count = Integer.MAX_VALUE;
    6.       for (int coin : coins) {
    7.           int res = coinChange(coins, amount - coin);
    8.           if (res == -1) continue;
    9.           count = Math.min(res + 1, count);
    10.       }
    11.       return count == Integer.MAX_VALUE ? -1 : count;
    12.   }
    14.   //2. 备忘录
    15.   int[] dp;
    16.   public int coinChange(int[] coins, int amount) {
    17.       if (amount < 0) return -1;
    18.       if (amount == 0) return 0;
    19.       dp = new int[amount + 1];
    20.       return recur(coins, amount);
    21.   }
    23.   public int recur(int[] coins, int amount) {
    24.       if(amount < 0) return -1;
    25.       if(amount == 0) return 0;
    26.       if(dp[amount] != 0) return dp[amount];
    27.       int res = Integer.MAX_VALUE;
    28.       for(int coin : coins) {
    29.           int r = recur(coins, amount - coin);
    30.           if(r == -1) continue;
    31.           res = Math.min(res, r + 1);
    32.       }
    33.       dp[amount] = res == Integer.MAX_VALUE ? -1 : res;
    34.       return dp[amount];
    35.   }
    37.   //3. 动态规划，由于使用的dp[i-coin]不固定，所以无法优化dp数组
    38.   public int coinChange(int[] coins, int amount) {
    39.       if (amount < 0) return -1;
    40.       if (amount == 0) return 0;
    41.       //dp[i]表示amoutn所需的最少硬币个数
    42.       int[] dp = new int[amount + 1];
    43.       //初始化一个较大的值即可
    44.       for(int i = 1; i <= amount; i++) {
    45.           dp[i] = amount + 1;
    46.       }
    47.       for (int i = 1; i <= amount ; i++) {
    48.           for (int coin : coins) {
    49.               if (i - coin >= 0)
    50.                   dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
    51.           }
    52.       }
    53.       return dp[amount] == amount + 1 ? -1 : dp[amount];
    54.   }

    零钱兑换