Abstract：#动态规划#01背包
1. 题目
- 题目：LeetCode 494. 目标和
2. 代码
classSolution{public:intfindTargetSumWays(vector<int>&nums,inttarget){inttotalSum=accumulate(nums.begin(),nums.end(),0);if(totalSum<abs(target)||((totalSum&1)^(target&1))==1){return0;}intsum=(totalSum+target)>>1;vector<int>dp(sum+1,0);dp[0]=1;for(autonum:nums){for(intj=sum;j>=num;--j){dp[j]+=dp[j-num];}}returndp[sum];}};3. 心得
- 剪枝策略：有两个剪枝方法其实很容易想到。一是target的绝对值不能超过备选数总和，否则无论如何也无法表示，返回0；二是备选数总和的奇偶性仅取决于数的绝对值，和加减操作无关，所以可以先验证target是否与备选数总和奇偶性一致，如果不一致则无法被表示，直接返回0。看似很简单的剪枝策略在题目判定时能够节省不少时间，所以今后在处理类似问题时不妨先从相反方向考虑一下，能否从显而易见的例子能够归纳出一些剪枝策略放在开头。
- 分组思想转换成01背包问题：我想到过能否将备选数分成正负两组，只处理其中一组那么剩下一组就自然被决定了，但最后还是因为纠结于如何判断数字“是正是负”（而非“选或不选”）没有做出来。事实上，设所有正数之和为P，所有负数绝对值之和为N，则P - N = target。又因为P + N = totalSum，两式相加得2P = totalSum + target，即P = (totalSum + target) / 2。因此，问题转化为：从数组中选出若干个数（对应正号部分），使其和等于P，有多少种选法？这就是经典的01背包求方案数问题。从标答思路可以看出，如何充分利用已知信息表达**“选或不选”**这一操作，是转化成01背包问题的关键。
- 判断奇偶性：利用&1可以快速判断是奇是偶。
4. 相关题目
- LeetCode 1049. 最后一块石头的重量
- bytedance-006. 夏季特惠
