LeetCode刷题实战494：目标和-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 目标和，我们先来看题面：

https://leetcode-cn.com/problems/target-sum/

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".
Return the number of different expressions that you can build, which evaluates to target.

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

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

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

示例

示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：
输入：nums = [1], target = 1
输出：1

解题

https://www.cnblogs.com/thefatcat/p/12872630.html

思想：动态规划

借鉴0-1背包，使用dp[i][j]记录选用nums中0-i个数字，组成目标为j时的方法数。

状态转移方程为：dp[i][j] = dp[i-1][j-nums[i] + dp[i-1][j+nums[i]

下表为dp[len][t]的表格，其中len=nums.size(),t=2*sum+1(sum为nums中所有元素的和),绿色表格为最终所求的方法数。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for(int i=0;i            sum += nums[i];
        if(abs(S) > abs(sum))
            return 0;
        int t = sum * 2 + 1; //注意t的取值
        int len = nums.size();
        vector<vector<int>> dp(len,vector<int>(t));
        if(nums[0] == 0)
            dp[0][sum] = 2;
        else{
            dp[0][sum + nums[0]] = 1;
            dp[0][sum - nums[0]] = 1;
        }
        for(int i = 1;i < nums.size();i++)
            for(int j = 0;j < t;j++){
                int l = (j - nums[i]) >= 0 ? j-nums[i] : 0;
                int r = (j + nums[i]) < t ? j+nums[i] : 0;
                dp[i][j] = dp[i-1][l] + dp[i-1][r];
            }
        return dp[nums.size()-1][sum + S];
    }
};