Leetcode 494. 目标和 动态规划-01背包

原题链接：Leetcode 494. 目标和

做这个题注意两点：

1. 边界条件：dp[0][0]=1;当考虑0个元素时，他们的和为0的方案数为1
2. 内循环j从0开始，表示他们的和为0的个数

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n=nums.size();
        int sum=0;
        for(auto x:nums) sum+=x;
        // 原题的意思即把数组分为两个子数组，让这两个子数组的差=target
        // 假设数组的和为sum, 子数组1的和为a, 那么子数组2的和就是sum-a
        // 要让他们的差是target，即a-(sum-a)=target，2a=sum+target
        // 那么原题就可以转换为：在nums数组中，找到子数组的和为a的个数
        if(target>sum || sum+target<0 || (sum+target)%2!=0) return 0;
        int a=(sum+target)/2;
        // dp[i][j]表示在nums数组前i个元素中，子数组的和为a的方案个数
        vector<vector<int>> dp(n+1,vector<int>(a+1,0));
        // 边界条件：当考虑0个元素时，他们的和为0的方案数为1
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            // 注意这里j从0开始，表示他们的和为0的个数
            for(int j=0;j<=a;j++){
                dp[i][j]=dp[i-1][j];
                if(j>=nums[i-1]){
                    dp[i][j]+=dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][a];
    }
};

空间优化: 注意，01背包问题，内循环倒序

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n=nums.size();
        int sum=0;
        for(auto x:nums) sum+=x;
        // 原题的意思即把数组分为两个子数组，让这两个子数组的差=target
        // 假设数组的和为sum, 子数组1的和为a, 那么子数组2的和就是sum-a
        // 要让他们的差是target，即a-(sum-a)=target，2a=sum+target
        // 那么原题就可以转换为：在nums数组中，找到子数组的和为a的个数
        if(target>sum || sum+target<0 || (sum+target)%2!=0) return 0;
        int a=(sum+target)/2;
        // dp[j]表示在nums数组中，子数组的和为a的方案个数
        vector<int> dp(a+1,0);
        // 边界条件：初始化，当考虑0个元素时，他们的和为0的方案数为1
        dp[0]=1;
        for(int i=0;i<n;i++){
            // 注意这里j从0开始，表示他们的和为0的个数
            for(int j=a;j>=nums[i];j--){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[a];
    }
};