动态规划--零钱兑换问题_硬币兑换问题动态规划

零钱兑换

内容

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

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

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

思路

硬币数量无限，有面额，金额是固定的，最少多少种凑法，感觉有点类似背包问题，在物品数量无限的情况下，给出物品大小，背包大小，有多少种装法。但这里是最少物品数量，不考虑物品种类数，所以定义dp数组时，试着直接忽略种类这个维度。
定义dp数组，dp[j]代表在大小为j的情况下，最少花费了dp[j]个硬币。
考虑状态转移方程

• 装第i种硬币，为了使得总硬币数最少，我们只取1枚，dp[j] = dp[j-第i种硬币的面额]+1
• 不装，dp[j] = dp[j]
  考虑边界条件
• 大小为0的情况下，花费自然为0
• 硬币的最小面值为1，那么在金额最大为amount的情况下，最多需要amount枚，加个常数即代表最大值。

代码

public int coinChange(int[] coins, int amount) {
    if(amount==0)
        return 0;
    int[] dp = new int[amount+1];
    Arrays.fill(dp,amount+1);
    dp[0] = 0;
    for(int i=0;i<amount+1;i++){
        for(int coin:coins){
            if(i-coin>=0)
                dp[i] = Math.min(dp[i],dp[i-coin]+1);
        }
    }
    return dp[amount]==amount+1?-1:dp[amount];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

零钱兑换Ⅱ

内容

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

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

思路

无限硬币，硬币有面值，有限金额，可以想到，有限大小的背包，去装一堆不限量的物品，每个物品有着相应的大小，问有多少种正好装满的装法。
所以，可以借鉴背包问题的dp数组设置方法，设dp[i][j]代表在使用i种硬币，达到j金额的情况下，有dp[i][j]种装法。
下面考虑状态转移方程，这个问题里，能做选择的是装不装第i种硬币，所以方程如下：

• 不装，dp[i][j]还是之前的结果dp[i-1][j]
• 装，dp[i][j]则得加上装的装法，即dp[i][j] = dp[i-1][j] + dp[i][j-第i种硬币的面值]

接下来，考虑边界条件
一开始，

• 如果硬币数为0，金额随便，那么装法为0，dp[0][j]=0
• 如果金额为0，硬币随便选，那么每种硬币都有一种装法，即，不装，所以，dp[i][0]=1

代码

public int change(int amount, int[] coins) {
   int len = coins.length;
   int[][] dp = new int[len+1][amount+1];
   for(int i=0;i<=len;i++)
       dp[i][0]=1;
   for(int i=1;i<=len;i++){
       for(int j=1;j<=amount;j++){
           if(j-coins[i-1]>=0){
               dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
           }else{
               dp[i][j] = dp[i-1][j];
           }
       }
   }
   return dp[len][amount];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//空间压缩
public int change(int amount, int[] coins) {
    int len = coins.length;
    int[] dp = new int[amount+1];
    dp[0] = 1;
    for(int i=1;i<=len;i++)
    {
        for(int j=1;j<=amount;j++){
            if(j-coins[i-1]>=0)
                dp[j] = dp[j]+dp[j-coins[i-1]];
           
        }
    }
    return dp[amount];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15