代码随想录三十七天 完全背包二维 完全背包一维 518. 零钱兑换 II 377. 组合总和 Ⅳ

完全背包二维

初始化和dp方程变化了。

#include <iostream>
#include <vector>
using namespace std;int main() {int n, bagWeight;int w, v;cin >> n >> bagWeight;vector<int> weight(n);vector<int> value(n);for (int i = 0; i < n; i++) {cin >> weight[i] >> value[i];}vector<vector<int>> dp(n, vector<int>(bagWeight + 1, 0));// 初始化for (int j = weight[0]; j <= bagWeight; j++)dp[0][j] = dp[0][j - weight[0]] + value[0];for (int i = 1; i < n; i++) { // 遍历物品for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量if (j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);}}cout << dp[n - 1][bagWeight] << endl;return 0;
}

完全背包一维

1. 首先和 01背包的dp方程不一样了

2. 其次，这里的遍历顺序要是正的。如图所示，要使用的上一行的元素在自己的右边，倒着遍历就覆盖了。

#include <iostream>
#include <vector>
using namespace std;int main() {int N, bagWeight;cin >> N >> bagWeight;vector<int> weight(N, 0);vector<int> value(N, 0);for (int i = 0; i < N; i++) {int w;int v;cin >> w >> v;weight[i] = w;value[i] = v;}vector<int> dp(bagWeight + 1, 0);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]);}
}cout << dp[bagWeight] << endl;return 0;
}

完全背包的简单应用，是组合数。

写方法数的时候有的时候会忘记初始化dp[0]=1，用一维数组写的时候，想一下第一排的内容。

func change(amount int, coins []int) int {//完全背包  求方法数  正序遍历//一维版本dp:=make([]int,amount+1) //初始化 写之前想一下第一排是什么内容dp[0]=1  //方法数这里就是1  //初始化for i:=0;i<len(coins);i++{for j:=coins[i];j<=amount;j++{dp[j]=dp[j]+dp[j-coins[i]]}}return dp[amount]}

func combinationSum4(nums []int, target int) int {//代码随想录那个不好理解//爬楼梯的方式好理解。这个是Leetcode70的进阶版本。//原先爬楼梯，一次只能爬1格或者是2格。f[n]=f[n-1]+f[n-2]。相当于nums=[1,2]//这题是爬楼梯，一次能爬1格，2格，3格dp:=make([]int,target+1) //dp表示爬到某格有多少种方法dp[0]=1  //初始化，爬0格有一种方法，什么都不做for i:=1;i<=target;i++{for _,num:=range nums{if i>=num {dp[i]+=dp[i-num]}}}return dp[target]
}
/*
直观的操作过程
dp[0] = 1 （初始化）dp[1] = dp[0] ① → 1dp[2] = dp[1] + dp[0] → 1 + 1 = 2dp[3] = dp[2] + dp[1] + dp[0] → 2 + 1 + 1 = 4dp[4] = dp[3] + dp[2] + dp[1] → 4 + 2 + 1 = 7
*/