题目来源
本题来源为：
题目描述
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
算法原理
先将问题转化成背包问题：
1.状态表示
经验+题目要求
对于本题而言就是：
dp[i][j]表示：从前i个数中选，总和正好等于j,一共有多少种选法
2.状态转移方程
还是从最后位置分情况讨论：
跟01背包问题没区别：
因此状态方程为：
3.初始化
跟01背包问题基本一样：
4.填表顺序
从上往下
5.返回值
dp[n][a]
代码实现
动态规划的代码基本就是固定的四步：
1.创建dp表 2.初始化 3.填表 4.返回值
本题完整代码实现：
class Solution { public: int findTargetSumWays(vector<int>& nums, int target) { int sum=0; for(auto x:nums) sum+=x; int aim=(sum+target)/2; //处理一下边界条件 if(aim<0||(sum+target)%2) return 0; int n=nums.size(); //创建dp表 vector<vector<int>> dp(n+1,vector<int>(aim+1)); //初始化 dp[0][0]=1; //填表 for(int i=1;i<=n;i++) { for(int j=0;j<=aim;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][aim]; } };
空间优化
代码实现:
class Solution { public: int findTargetSumWays(vector<int>& nums, int target) { int sum=0; for(auto x:nums) sum+=x; int aim=(sum+target)/2; //处理一下边界条件 if(aim<0||(sum+target)%2) return 0; int n=nums.size(); //创建dp表 vector<int> dp(aim+1); //初始化 dp[0]=1; //填表 for(int i=1;i<=n;i++) { for(int j=aim;j>=nums[i-1];j--) { dp[j]+=dp[j-nums[i-1]]; } } return dp[aim]; } };
