代码随想录第38天|动态规划

1049. 最后一块石头的重量 II

参考

备注: 当物体容量也等同于价值时, 01背包问题的含义则是利用好最大的背包容量sum/2, 使得结果尽可能的接近或者小于 sum/2
等价: 尽可能的平分成相同的两堆, 其差则为结果, 比如 (a+b+c)-d, (a+c)-(b+d) , 最终的结果是一堆减去另外一堆的和, 问题则转换成01背包

class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int sum = 0;for (int i = 0; i < stones.size(); i++) {sum += stones[i];}vector<int> dp(sum / 2 + 1, 0);for (int i = 0; i < stones.size(); i++) {for (int j = sum / 2; j >= 0; j--) {if (j - stones[i] >= 0) {dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);}}}return (sum - dp[sum / 2]) - dp[sum / 2];}
};

---

494. 目标和

回溯法会超时

转换成01背包问题:

• A + B = sum
• A - B = target
• A = (target + sum) / 2
• B = (sum - target) / 2
  其中A相当于weigh, nums[i]相当于价值
  当 A = (target + sum) / 2 向下取整时, 说明不存在结果
  当 abs(target) > sum 时不存在

五部曲:

1. dp[j]: 填满j（包括j）这么大容积的包，有dp[j]种方法 (假设A为容量)
2. 
3. 初始化: dp[0] = 1

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for (int i = 0; i < nums.size(); i++) {sum += nums[i];}int A = (target + sum) / 2;if ((target + sum) % 2) return 0;if (abs(target) > sum) return 0;vector<int>dp(A + 1, 0);dp[0] = 1;for (int i = 0; i < nums.size(); i++) {for (int j = A; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[A];}
};

---

474.一和零