代码随想录打卡第三十天 动态规划
学习目标：
- 学习动态规划
学习内容：
- 01背包问题
学习时间：
- 2025-06-17 周二晚上
学习产出：
背包问题
01背包：每件物品只能用一次，对于每件物品，即放或者不放。
完全背包：物品可以一直放。
01背包：
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
可以得到递推公式：对于第i件物品，对于重量为j的背包产生的最大价值为：不放入该件物品时的最大价值dp[i-1][j]与放入该物品时的最大价值dp[i-1][j-weight[i]]+values[i]的最大值，即：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
如果我们把dp[i-1]的数据先copy到第i行，那么得到递推公式：
dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
那完全可以我们只维护一行数组，每次遍历物品时用上一层的dp[j]来进行更新即可，更新为一维数组递归公式为：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
右边的dp[j]表示上一层即dp[i-1][j]得到的结果注意，如果用一维数组表示，那么只能倒序才能保证每个物品只放入了一次，具体可以自己推导。
- 416. 分割等和子集
解题思路
先求出目标和以及初始化dp[target]还是很直观。但是对于初次接触背包问题来讲，在想dp[j]表示的涵义时没想明白。dp[j]应该表示为：当背包最大容量为j时，放入i和不放入i所能产生的最大价值是多少。如果最大容量为target且当前所能产生的最大价值为target时，表示存在。转化为本题为，加入在不超过当前最大和的情况下，放入哪些元素能使的当前的目标和最大（接近target）
`class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;boolean result = false;for(int i = 0;i<nums.length;i++) {sum+=nums[i];}if(sum % 2 != 0) {return result;}int target = sum / 2;int[] dp = new int[target+1];for(int i = 0 ; i < nums.length ; i++) {for (int j = target ; j >= nums[i] ; j--) {dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);if(dp[j] == target) {result = true;}}}return result;
}
}`