代码随想录算法训练营第四十二天|01背包问题、416. 分割等和

01背包问题

分为二维数组和一维数组，一维有点绕

416. 分割等和子集

动规五部曲：

确定dp数组以及下标的含义

01背包中，dp[j] 表示： 容量为j的背包，所背的物品价值最大可以为dp[j]。

dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]

如果背包容量为target， dp[target]就是装满 背包之后的重量，所以 当 dp[target] == target 的时候，背包就装满了

确定递推公式

01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

dp数组如何初始化

dp[0]一定是0

确定遍历顺序

使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历

// 开始 01背包for(inti=0;i<nums.size();i++){for(intj=target;j>=nums[i];j--){// 每一个元素一定是不可重复放入，所以从大到小遍历dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);}}