Abstract#动态规划#01背包1. 题目题目LeetCode 494. 目标和2. 代码classSolution{public:intfindTargetSumWays(vectorintnums,inttarget){inttotalSumaccumulate(nums.begin(),nums.end(),0);if(totalSumabs(target)||((totalSum1)^(target1))1){return0;}intsum(totalSumtarget)1;vectorintdp(sum1,0);dp[0]1;for(autonum:nums){for(intjsum;jnum;--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. 夏季特惠