Leetcode 零钱兑换问题_零钱兑换 leetcode

322.零钱兑换

说起零钱兑换问题，首先不得不提的就是完全背包问题

完全背包问题是指有 n 个物体，每个物体有各自的体积和价值，区分于01背包的是，每个物体其数量是无限的。求指定体积的背包能放物体的最大价值。

这里给出完全背包的核心代码：

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j < bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}
1
2
3
4
5
6

其中 dp[i] 是指体积为 i 的背包所能背的物品的最大价值

那么本题与完全背包有何关系呢？

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

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

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

每个硬币数量是无限的对应完全背包中物品数量是无限的
而总金额amount对应了背包的体积

但是我们又发现该题与完全背包的不同之处在于该题是能凑成该金额的最少金币的数量，而完全背包则是这些物品放入背包后的最大价值。

分析本题：

1.初始化，当总金额为0时，所需的硬币数量显然是0，故dp[0]=0 , 由于求的是最小值，故将 dp数组中其他元素赋值为最大值

2.递推式，我们可以借用完全背包的思想，体积和价值均为coins数组，由于每遍历一个新的物体，更新 dp下标 从coins[i]到amount
若加入该硬币 ， dp[j] = dp[j-coins[i]] +1;
若不加入该硬币：dp[j] = dp[j];
故递推式为 dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
又因为 dp[j-coins[i]] 不一定被遍历
故需要加一个条件判断：
总递推式：
if(dp[j-coins[i]]!=Integer.MAX_VALUE)
dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);

3.返回值，若遍历完后，发现 dp[amount] 为Integer.MAX_VALUE , 则说明没有方法凑到这个总金额，返回-1；否则返回 dp[amount]即可
return dp[amount] == Integer.MAX_VALUE?-1:dp[amount];

总代码：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        dp[0] = 0;
        for(int i = 1;i<dp.length;i++) dp[i] = Integer.MAX_VALUE;
        for(int i = 0;i<coins.length;i++)
        for(int j = coins[i];j<=amount;j++){
            if(dp[j-coins[i]]!=Integer.MAX_VALUE) 
            dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
        }
        return dp[amount] == Integer.MAX_VALUE?-1:dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

518.零钱兑换Ⅱ

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

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

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

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

看到这到题，首先我想到了以前做过的组合总和Ⅳ，可以看我组合总和那篇博客，我将它规为爬楼梯问题。如果amount视为总楼梯的层数，而coins数组视为一次能爬的层数，该题可视为爬楼梯问题。

但是我发现该题与爬楼梯问题又有不同的地方，该题是不区分顺序，即为组合；而爬楼梯问题则是区分顺序，即为排列。

每个硬币数量是无限的对应完全背包中物品数量是无限的
而总金额amount对应了背包的体积，所以我想到了完全背包的思想

int[] dp = new int[amount+1]; dp[i]的意义是当总金额为i时，兑换的方式个数为dp[i]

1.初始化 由于当 dp下标为0时，只有一种方式，就是coins数组中各个硬币的数量均为0，故 dp[0] = 1

2.递推式 我们可以借用完全背包的思想，体积和价值均为coins数组，由于每遍历一个新的物体，更新 dp下标 从coins[i]到amount

若考虑该硬币 dp[j] = dp[j] + dp[j-coins[i]]
不考虑该硬币 dp[j] = dp[j]

故递推式为： dp[j] += dp[j-coins[i]];

3.返回值，返回 dp[amount] 即可

总代码：

class Solution {
    public int change(int amount, int[] coins) {
        g
        dp[0] = 1;
        for(int i = 1;i<=amount;i++)
        for(int j = 0;j<coins.length;j++){
            if(i>=coins[j]) dp[i] += dp[i-coins[j]];  
        }

        return dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

这里我给出组合总和Ⅳ，也就是爬楼梯代码，发现这两个题for循环遍历方式不同，可能就是排列与组合的差别

爬楼梯：

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int i = 1;i<=target;i++){
            for(int j = 0;j<nums.length;j++){
                if(i-nums[j]>=0) dp[i] += dp[i-nums[j]];
            }
        }
        return dp[target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12