LeetCode 494 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 + 或 - ，然后串联起所有整数，可以构造一个表达式：

例如，nums = [2, 1] ，可以在 2 之前添加 + ，在 1 之前添加 - ，然后串联起来得到表达式 +2-1 。
返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

动态规划

此处需要注意的是，要求对于每一个数字都需要添加一个 + 或 - 运算符。并且只包含 + 和 - 运算符，顺序并不会影响结果。此处依旧是按照0/1背包问题的方式进行问题的划分。

动态规划数组的定义：定一个数组 dp[2001] 其中 dp[i]=j 表示，在 0-0 元素中进行选择，能够得到值为 i-1000 的表达式有 j 个。
动态规划数组的推导：在第 k 次迭代中，从 0-k 的元素中生成表达式，相较于上一次，仅仅是多了元素 nums[k] ，那么对于 nums[k] 前的运算符只有 - 或 + 两种。那么 dp[i]=dp[i-nums[k]]+dp[i+nums[k]] 这样的更新方式，本质上就是在穷举，通过一个双for循环完成穷举。
动态规划数组的初始化：对于 dp[2001] 首先全部初始化为0，在处理第一个元素分别正负的问题 dp[1000+nums[0]]+=1 dp[1000-nums[0]]+=1 。
动态规划数组的遍历顺序：对于外层循环，需要不断将元素加入到表达式中，外层循环遍历 nums 中的元素。内层循环便利数组的中的元素。
举例验证： nums[2,1],target=1 初始时 dp[1002]=1,dp[998]=1 ，第一次迭代 dp[1001]=dp[1000]+dp[1002]=1 验证成立。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        vector<int> dp(2001,0);
        dp[1000-nums[0]]+=1;
        dp[1000+nums[0]]+=1;
        for(int i=1;i<nums.size();i++){
            vector<int> tmp=dp;
            for(int j=0;j<dp.size();j++){
                dp[j]=j-nums[i]>-1?tmp[j-nums[i]]:0;
                dp[j]+=j+nums[i]<2001?tmp[j+nums[i]]:0;
            }
        }
        return dp[1000+target];
    }
};

在上述的实现过程中，本质上是在使用动态规划的方式将表达式求值的全部可能都穷举了出来，实现的方式和回溯法类似，时间复杂度和空间复杂度都较大。

对问题进行转化：

对整个数组 nums 进行求和，最终的和值为，假设在总体的表达式中前置符号为的元素之和为，那么前置符号为的元素之和为，那么就有，对问题进行转换就得到：

$neg=\frac{sum-target}{2}$

也就将问题转化为了，在数组 nums 中选取元素，是的元素的和等于。上述假设都是建立在能够在数组 nums 中找到元素组合为表达式计算得到 target 的前提下，但若是不能找到任何方案，这样计算就会出现问题，因此需要增加一层判断，判断是否存在余数，若是存在余数说明不存在任何方案。

动态规划数组的定义：定义数组 dp[neg+1] 其中 dp[i]=j 表示，在 0-0 个元素中选取总和为 i 的方案有 j 种。
动态规划数组的推导：在第 k 次迭代中，从 0-k 个元素中进行选取，此处相较于上一次，仅有 nums[k] 这个元素，不同，对应两种方式：选取或不选。那么递推公式 dp[i]=dp[i]+dp[i-nums[k]] if i-nums[k]>=0 else dp[i]
动态规划数组的初始化：初始时全部初始化为0，然后 dp[nums[0]]=1(if nums[0]<=neg),dp[0]=1 。
数组的遍历顺序：在外层循环中将数组中的元素逐个添加，因此外层循从左向右遍历的数组，在内层循环中则是遍历动态规划数组，在计算 dp[i] 时需要使用 dp[i-nums[k]] 的值，从右向左遍历。
举例验证： nums={2,1},target=1 那么 neg=1 初始时 dp={1,0} 第一次迭代：dp[1]=dp[1]+dp[0]=1 验证正确。

代码实现：

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

回溯法实现：

int count=0;
int tmp=0;
void backTrack(vector<int>& nums,int target,int cur){
    if(cur==nums.size()){
        if(tmp==target) count++;
        return;
    }
    tmp+=nums[cur];
    backTrack(nums,target,cur+1);
    tmp-=nums[cur];
    tmp-=nums[cur];
    backTrack(nums,target,cur+1);
    tmp+=nums[cur];
}
int findTargetSumWays(vector<int>& nums, int target) {
    backTrack(nums,target,0);
    return count;
}

Mark's blogs

LeetCode-494-目标和

LeetCode 494 目标和

动态规划