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<nums.size();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];
}
};好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
上期推文：
腾讯云开发者
