代码随想录第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.一和零