代码随想录算法训练营 Day37 动态规划Ⅴ 完全背包 零钱兑换
动态规划
完全背包
纯的完全背包问题（只是背包）可以颠倒两次 for 循环的顺序
因为完全背包 dp 值由左边的状态推导而来的，两种遍历方法都能保证前面有数据
0-1 背包二维递推公式
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
完全背包二维递推公式
dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])
在于01背包是 dp[i - 1][j - weight[i]] + value[i] ，完全背包是 dp[i][j - weight[i]] + value[i])
主要原因就是 完全背包单类物品有无限个。
题目
52. 携带研究材料（第七期模拟笔试）
对比 0-1 背包问题，将遍历顺序改为正序遍历（第二次顺序）
1. Dp 表示容量 j 下的背包能装的最大价值
2. 递推公式同 0-1 背包问题，比较空出来空间不拿这个物品和拿了这个物品的最大价值
dp[i][j] = std::max(dp[i-1][j], dp[i-1][j-nums[i]] + value[i])
3. 初始化顺序第一行与第一列（数据从第一行开始推导的）
dp[i][0] = 0; dp[0][j]=dp[0][j-nums[0]] + value[0]
4. 遍历顺序为物品 - 背包 （正序遍历一维数组）
5. Dp 打印
#include<iostream>
#include<vector>int main() {int n = 0, v = 0;std::cin >> n >> v;std::vector<int> weight(n, 0);std::vector<int> value(n, 0);for (int i = 0; i < n; ++i) std::cin >> weight[i] >> value[i];// 初始化dp 单位j时最大的价值std::vector<std::vector<int>> dp(n, std::vector<int>(v+1, 0));for (int j = weight[0]; j <= v; ++j) dp[0][j] = dp[0][j - weight[0]] + value[0];// 遍历dpfor (int i = 1; i < n; ++i) {for (int j = 0; j <= v; ++j) {if (j < weight[i]) dp[i][j] = dp[i-1][j];else dp[i][j] = std::max(dp[i-1][j], dp[i][j - weight[i]] + value[i]);}}std::cout << dp[n-1][v] << std::endl;return 0;
}
518. 零钱兑换 II - 力扣（LeetCode）
背包问题求组和，不强调顺序
1. Dp 含义表示当前 i 个物品下装满 j 背包多少种方法
2. 递推公式类似于 0-1 背包组合问题 dp[i][j] = dp[i-1][j] + dp[i][j-nums[i]]
3. 初始化 dp[i][0]=1 第一行如果背包可以装下物品，则方法为 1，否则为 0
4. 遍历顺序默认即可先物品后背包（可以颠倒，一维情况不同）
一维情况下不能颠倒，先遍历物品再遍历背包求排列数，先遍历背包再遍历物品求组合数
5. 打印 dp
int change(int amount, vector<int>& coins) {int bagSize = amount;// dp数组定义 在i个物品下装满j由多少种方法std::vector<std::vector<uint64_t>> dp(coins.size(), std::vector<uint64_t>(bagSize+1, 0));// 初始化dpfor (int i = 0; i < coins.size(); ++i) dp[i][0] = 1;// 可以兑换 +1 方法for (int j = 0; j <= bagSize; ++j) if (j % coins[0] == 0) dp[0][j] = 1;// 遍历dpfor (int i = 1; i < coins.size(); ++i) {for (int j = 0; j <= bagSize; ++j) {if (coins[i] > j) dp[i][j] = dp[i-1][j];else dp[i][j] = dp[i-1][j] + dp[i][j - coins[i]];}}return dp[coins.size()-1][bagSize];
}
377. 组合总和 Ⅳ - 力扣（LeetCode）
完全背包的求排列问题，在上一题基础上变换遍历顺序即可
1. Dp 数组表示当前装满 j 背包多少种方法
2. 递推公式基于二维递推公式得出 dp[j]+=dp[j-nums[i]] i 表示物品 j 表示背包
3. 初始化 dp[0]=1
4. 遍历顺序先遍历背包再遍历物品求排列，先遍历物品再遍历背包求组合
5. 打印 dp
int combinationSum4(vector<int>& nums, int target) {// dpstd::vector<int> dp(target+1, 0);// 初始化dp[0] = 1;// dp遍历for (int j = 0; j <= target; ++j) {for (int i = 0; i < nums.size(); ++i) {if (j - nums[i] >= 0 && dp[j] <= INT_MAX - dp[j - nums[i]]) dp[j] += dp[j - nums[i]];}}return dp[target];
}
57. 爬楼梯（第八期模拟笔试）
爬楼梯进阶版，使用 dp 数组实现，求方法排列组合 121 和 211 两种方法
背包是 n 级台阶，物品是 m 上台阶方法，从 1 开始遍历因为题目要求
1. Dp 数组表示第 j 容量（楼梯）有多少种方法
2. 递推公式如上题，从之前的数据中累加的来 dp[j] += dp[j-nums[i]]
3. Dp 初始化 dp[0]=1
4. 遍历顺序先遍历背包再遍历物品
5. Dp 打印
#include<iostream>
#include<vector>int main() {int m = 0, n = 0;std::cin >> n >> m;// 定义dpstd::vector<int> dp(n+1, 0);dp[0] = 1;// 遍历dp 先遍历背包n，再遍历物品mfor (int j = 1; j <= n; ++j) {for (int i = 1; i <= m; ++i) {// 背包有空间的情况下if (j - i >= 0) dp[j] += dp[j - i];}}std::cout << dp[n] << std::endl;return 0;
}