代码随想录算法训练营第三十七天 | 动态规划 part05

问题的本质就是给定一个容量的背包，装满有多少种方法，递推公式是：dp[j] += dp[j - coins[i]]
但是这里有拓展的地方是遍历顺序，完全背包问题是可以调换两个for循环的顺序的，但是在这里不行。因为这里是组合问题，要先遍历物品，再遍历背包。如果是排列问题，要先遍历背包，再遍历物品。
对于先遍历物品，再遍历背包的遍历顺序来说，每次只会多去更新一个物品。类似于组合。
但是对于先遍历背包，再遍历物品的遍历顺序来说，每次都会从头区遍历物品，类似于排序。

class Solution {
public:int change(int amount, vector<int>& coins) {// 1. dp[j] 表示凑成总金额为j有dp[j]种方法// 2. 递推公式：dp[j] += dp[j - coins[i]]// 3. 初始化：dp[0] = 1, 其余为0vector<int> dp(amount + 1, 0);dp[0] = 1;for (int i = 0; i < coins.size(); ++i) {for (int j = coins[i]; j < amount + 1; j++) {dp[j] += dp[j - coins[i]];}}return dp[amount];}
};

这一题就是求得排列，与上题的区别就是for循环位置。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {// 1. dp[j] 表示凑成目标整数为j有dp[j]种方法// 2. 递推公式：dp[j] += dp[j - nums[i]]// 3. 初始化：dp[0] = 1, 其余为0vector<int> dp(target + 1, 0);dp[0] = 1;for (int j = 0; j < target + 1; j++) {for (int i = 0; i < nums.size(); ++i) {if (j >= nums[i] && dp[j] < INT_MAX - dp[j - nums[i]])dp[j] += dp[j - nums[i]];}}return dp[target];}
};

可以将爬楼梯抽象为完全背包问题。背包容量是楼梯数，物品的重量就是1-m，每次爬多少级台阶，物品的价值是爬到j台阶数有多少种方法。在本题中，是一种排列问题，而不是组合问题。

#include <iostream>
#include <vector>using namespace std;void completebag() {int target, step;cin >> target >> step;vector<int> dp(target + 1, 0);dp[0] = 1;for (int j = 0; j < target + 1; j++) {for (int i = 1; i < step + 1; ++i) {if (j >= i)dp[j] += dp[j - i];}}cout << dp[target];
}int main() {completebag();return 0;
}