零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：

输入：coins = [2], amount = 3
输出：-1
示例 3：

输入：coins = [1], amount = 0
输出：0

思考

dp数组含义及其下标意义

dp[j]: 表示使用硬币(其硬币面值小于金额j)凑满金额j的最小硬币数

dp数组初始化

首先我们对coins数组进行排序

这里我们定义

• -1代表不能凑满金额j
• 0 代表amount等于0时，不需要掏出硬币

首先我们初始化dp[0] = 0;

dp[1 …coins[0]-1 ] 赋值为-1，因为在这个总钱数j已经比最小的硬币还小了。

其次初始化 dp[ coins[0] ] =1，因为这个总钱数j正好等于第一个硬币的价格 所以最少需要一个硬币

其余数 = Integer.Maxval;

状态转移方程

dp[j] = dp[j-coins[i]] + 1;

意思是 我们需要求得凑成金额为j的最小硬币数，我们现在有硬币coins[i]，所以我们只需要知道凑成

j-coins[i]的最小硬币数即可。

所以当coins[i]≤j时，我们需要选成一个最小的

dp[j] =Min{dp[j-coins[0]] + 1，dp[j-coins[1]] + 1，…，dp[j-coins[i]] + 1}

即可。

public int coinChange(int[] coins, int amount) {
        // 排序数组
        Arrays.sort(coins);
        if(amount==0) return 0;
        if(amount<coins[0]) return -1;

        // 创建dp数组
        int[] dp=new int[amount+1];

        // 初始化dp数组
        dp[0] = 0;
        for (int i=1;i<=coins[0];i++){
            if(i==coins[0]) dp[i] = 1;
            else dp[i] = -1;
        }
        for (int i=coins[0]+1;i<=amount;i++){
            dp[i] = Integer.MAX_VALUE;
        }
        // 完善dp数组
        for (int i=coins[0]+1;i<=amount;i++){
            for (int coin : coins){
              if(coin<=i){
                  // 如果当前物品等于背包容量
                  if(i==coin) {
                      dp[i] = 1;
                      break;
                  }
                  // 如果当前 i-coin 背包没法装时，也就是i-coin=-1
                  if(dp[i-coin]==-1) continue;
                  int temp = dp[i-coin]+1;
                  if(temp<dp[i]) dp[i] =temp;
              }
            }
            // 意思是 前面没有一个dp[i-coin]是可用的
            if(dp[i]==Integer.MAX_VALUE) dp[i] =-1;
        }
        for (int i=0;i<=amount;i++){
            System.out.println("index="+i+","+dp[i]+ " ");
        }
        return dp[amount];
 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42