题目

image.png

思路

  • 该题型属于完全背包类型
  • 思路一：暴力递归，想要避免出现重复情况，要遍历每种硬币不同兑换金额下的可能性，也就是每次递归只使用一种硬币，但是它遍历使用它的不同数量，而不是遍历不同硬币下的可能性，第二种方式会导致重复。
  • 思路二：备忘录
  • 思路三：动态规划，定义dp[i][j]表示使用i种硬币可以表示金额j的所有可能性，不管当前硬币是否满足兑换金额都会有dp[i][j] = dp[i-1][j]，i中所满足的情况肯定建立在i-1中的基础之上，当当前硬币满足兑换金额再加上dp[i][j - coin]的可能性即可

  • 思路四：优化dp数组的动态规划，画图判断是否可以优化

    代码

    1.   //1.暴力递归超时
    2.   public int change(int amount, int[] coins) {
    3.      if (amount == 0) return 1;
    4.      if (amount < 0) return 0;
    5.      return recur(amount, coins, new HashMap<>());
    6.   }
    8.   //记录已使用的key，用于去重处理
    9.   Set<String> used = new HashSet<>();
    10.   public int recur(int amount, int[] coins ,Map<Integer, Integer> map) {
    11.      if (amount == 0) {
    12.          StringBuilder key = new StringBuilder();
    13.          for (int coin : coins) {
    14.              key.append(map.getOrDefault(coin, 0)); 
    15.          }
    16.          if (!used.contains(key.toString())) {
    17.              used.add(key.toString());
    18.              return 1;
    19.          }
    20.          return 0;
    21.      }
    22.      if (amount < 0) return 0;
    23.      int count = 0;
    24.      for (int coin : coins) {
    25.          if (amount - coin >= 0) {
    26.               map.put(coin, map.getOrDefault(coin, 0) + 1);
    27.               count += recur(amount - coin, coins, map);
    28.               map.put(coin, map.getOrDefault(coin, 0) - 1);
    29.          }
    30.      }
    31.      return count;
    32.   }
    34.   //1.暴力递归超时
    35.   public int change(int amount, int[] coins) {
    36.      if (amount == 0) return 1;
    37.      if (amount < 0) return 0;
    38.      return recur(amount, coins, 0);
    39.   }
    41.   public int recur(int amount, int[] coins, int index) {
    42.       if (amount == 0) return 1;
    43.       if (amount < 0 || index >= coins.length) return 0;
    44.       int k = amount / coins[index], count = 0;
    45.       for (int i = 0; i <= k; i++) {
    46.           count += recur(amount - i * coins[index], coins, index + 1);
    47.       }
    48.       return count;
    49.   }
    51.   //2. 备忘录
    52.   Map<String, Integer> map = new HashMap<>();
    53.   public int change(int amount, int[] coins) {
    54.      if (amount == 0) return 1;
    55.      if (amount < 0) return 0;
    56.      return recur(amount, coins, 0);
    57.   }
    59.   public int recur(int amount, int[] coins, int index) {
    60.       if (amount == 0) return 1;
    61.       if (amount < 0 || index >= coins.length) return 0;
    62.       String key = coins[index] + "-" + amount;
    63.       if (map.containsKey(key)) return map.get(key);
    64.       int k = amount / coins[index], count = 0;
    65.       for (int i = 0; i <= k; i++) {
    66.           count += recur(amount - i * coins[index], coins, index + 1);
    67.       }
    68.       map.put(key, count);
    69.       return count;
    70.   }
    72.   //3.动态规划
    73.   public int change(int amount, int[] coins) {
    74.      //dp[i][j]表示使用小于等于i种硬币可以表示j金额的所有可能性
    75.      int[][] dp = new int[coins.length + 1][amount + 1];
    76.      // 有一种方案凑成 0 元，那就是 一个也不选
    77.      dp[0][0] = 1;
    78.      for (int i = 1; i <= coins.length; i++) {
    79.           for (int j = 0; j <= amount; j++) {
    80.               //不管是否使用i种金额能凑出几种可能性，至少可能性是大于等于i-1种金额凑出的可能性
    81.               dp[i][j] = dp[i - 1][j];
    82.               if (j >= coins[i - 1])
    83.                   dp[i][j] += dp[i][j - coins[i - 1]];
    84.           }
    85.       }
    86.       return dp[coins.length][amount];
    87.   }
    89.   //4.优化dp数组的动态规划，由于使用了前一行的dp数组和前一个元素，所以是可以优化的，画图就很快发现
    90.   public int change(int amount, int[] coins) {
    91.      if (amount == 0) return 1;
    92.      if (amount < 0) return 0;
    93.      int[] dp = new int[amount + 1];
    94.      dp[0] = 1;
    95.      for (int coin : coins) {
    96.           for (int i = 0; i <= amount; i++) {
    97.               if (i - coin >= 0)
    98.                   dp[i] += dp[i - coin];
    99.           }
    100.       }
    101.       return dp[amount];
    102.   }

零钱兑换 II