代码随想录算法训练营day37 |完全背包理论基础、518. 零钱兑换 II 、377. 组合总和 Ⅳ、70. 爬楼梯 （进阶）

碎碎念：加油！！
参考：代码随想录

完全背包理论基础

完全背包的每个物品可以使用无数次。
体现在代码上，只需要在01背包代码的基础上，把第二个for循环改为正序遍历。
对于纯完全背包类问题遍历物品和遍历背包的这两层for循环位置可以颠倒。

518. 零钱兑换 II

题目链接

518. 零钱兑换 II

思想

每个钱币可以使用无限次，所以这是一个完全背包问题。
本题求的是组合数，不强调元素之间的顺序。
动态规划五部曲：

1. 确定dp数组以及下标的含义：dp[j]，装满容量为j的背包有dp[j]种方法，最终要求dp[amount]。
2. 确定递推公式：dp[j] += dp[j-coins[i]]
3. dp数组的初始化：dp[0]=1，根据题目后台样例，dp[0]应该是1。非0下标的值初始化为0。
4. 确定遍历顺序：两层for循环，第一层for循环遍历物品，第二层for循环遍历背包。遍历背包的时候正序遍历。这样遍历得到的是组合数。
5. 打印dp数组：主要用来debug。

题解

// cpp
class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1, 0);dp[0] = 1;for (int i = 0; i < coins.size(); i++) {for (int j = coins[i]; j <= amount; j++) {dp[j] += dp[j - coins[i]];}}return dp[amount];}
};

# python
class Solution:def change(self, amount: int, coins: List[int]) -> int:dp = [0] * (amount + 1)dp[0] = 1for coin in coins:for j in range(coin, amount + 1):dp[j] += dp[j - coin]return dp[amount]

反思

如果先遍历背包再遍历物品，得到的是排列数。

377. 组合总和 Ⅳ

题目链接

377. 组合总和 Ⅳ

思想

数组中每个元素都可以使用无限次，所以这是完全背包问题。且本题强调元素顺序，所以事实上是排列问题。
本题和上一题区别就在于本题强调元素的顺序。
那么本题就要先遍历背包再遍历物品。

题解

// cpp
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target + 1);dp[0] = 1;// 排列，先遍历背包，再遍历物品for (int i = 0; i <= target; i++) {for (int j = 0; j < nums.size(); j++) {if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) { // 避免整数溢出dp[i] += dp[i - nums[j]];}}}return dp[target];}
};

# python
class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:dp = [0] * (target + 1)dp[0] = 1for i in range(1, target + 1):for j in range(len(nums)):if i - nums[j] >= 0:dp[i] += dp[i - nums[j]]return dp[target]

反思

注意判断当前数值能否用于组合，写C++的时候注意防止整数溢出。

70. 爬楼梯 （进阶）

题目链接

70. 爬楼梯 （进阶）

思想

本题可以抽象为完全背包问题，而且是结果要求是排列的问题，因为先走一步，再走两步和先走两步再走一步是两种不同的走法。

动态规划五部曲：

1. 确定dp数组以及下标的含义：dp[i]，爬到第j层有dp[i]种方法。
2. 确定递推公式：dp[i] += dp[i - j]
3. dp数组的初始化：dp[0]=1，如果dp[0] = 0，那么其他数值都是0。
4. 确定遍历顺序：两层for循环，第一层for循环遍历背包，第二层for循环遍历物品。遍历背包的时候正序遍历。
5. 打印dp数组：主要用来debug。

题解

#include <iostream>
#include <vector>
using namespace std;
int main() {int n, m;while (cin >> n >> m) {vector<int> dp(n + 1, 0);dp[0] = 1;// 完全背包问题 所以要正序遍历// 求的是排列 所以先遍历背包再遍历物品for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (i - j >= 0) dp[i] += dp[i - j];}}cout << dp[n] << endl;}
}

# python
n,m = list(map(int,input().split(' ')))
dp = [0] *(n+1)
dp[0] = 1
for j in range(1, n+1):for i in range(1, m+1):if j >= i:dp[j] += dp[j-i]print(dp[n])

反思

注意和之前做过的普通的爬楼梯题目进行对比，之前的是比较简单的动态规划问题，本题变成了一个需要输出排列的完全背包问题。