题目描述

image.png

解题思路

本题和组合题中的零钱兑换都是多重背包问题，可以被多次放入。
但此题求得是组成总和的最少总个数，二零钱兑换II求的是组成该钱的总方法数，所以dp含义和递推公式有不一样的地方。

  • 确定dp数组以及下标的含义

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]。

  • 递推公式

得到dp[j]（考虑coins[i]），只有一个来源，dp[j - coins[i]]（没有考虑coins[i]）。
凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
而零钱兑换II求得是方法，所以递推公式不一样。

  • 初始化

首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;其他初始化为Integer最大值，防止在递推公式中会被覆盖。

  • 确定遍历顺序

本题不强调是排列还是组合问题。所以不讲究背包和物品的顺序。

  • 举例推导dp数组

以输入：coins = [1, 2, 5], amount = 5为例
image.pngdp[amount]为最终结果

  1. public int coinChange(int[] coins, int amount) {
  2.     // dp[i]表示背包为i最少的硬币的个数为dp[i]
  3.     int[] dp = new int[amount + 1];
  4.     Arrays.fill(dp, Integer.MAX_VALUE);  // 全部初始化为最大，防止递推公式失效
  5.     dp[0] = 0;  // 0表示没有硬币个数凑成
  7.     // 也可以背包放外边
  8.     for (int i = 0; i < coins.length; i++) { // 先遍历物品
  9.         for (int j = coins[i]; j <= amount; j++) {
  10.             // 只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
  11.             // 因为有些是不存在的组合
  12.             if (dp[j - coins[i]] != Integer.MAX_VALUE) {
  13.                 dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
  14.             }
  15.         }
  16.     }
  18.     // 最后进行判断，是否能被兑换
  19.     return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
  20. }