1049. 最后一块石头的重量 II向背包问题的转化方式根据题意最终的结果就是把石头分成最接近的两堆然后做差。所以转化为背包问题就是往容器为sum/2的背包里面放最大重量的石头也就是把石头价值设为重量。最终dp[sum/2]的值就是分成的两堆中比较小的堆重然后sum-dp[sum/2]就是比较大的堆重二者做差就是最终结果。class Solution { public: int lastStoneWeightII(vectorint stones) { vectorint dp(15001,0); int sum0; for(int i:stones) sumi; int target sum/2; for(int i0;istones.size();i){ for(int jtarget;jstones[i];--j){ dp[j]max(dp[j],dp[j-stones[i]]stones[i]); } } return sum-dp[target]-dp[target]; } };494. 目标和转化成背包问题的思路本题可化为划分两个子集的问题left为加号集总和right为减号集总和求其中一个集合的放物品方式即可得到结果因为一个集合固定了另外一个集合也是固定的两个公式leftrightsumleft-righttarget推导出left(sumtarget)/2所以left可作为背包的最大容量然后nums中的元素即为物品转化为了背包问题动规五部曲-一维1.dp[j]的含义容量为j的背包在i个物品下选取装满背包有多少种方式2.递推公式:dp[j]dp[j-nums[i]]解释dp[j] 的含义是前 i-1 个物品装满容量 j 的方式数量dp[j-nums[i]] 是前 i-1 个物品装满容量 j-nums[i] 的方式数量。把dp[j]拆分为两种情况(1)选择当前物品 nums[i]那么这些能够装满 j-nums[i] 的方案每一种都可以再加上当前物品变成一种装满容量 j 的新方案。所以当前 dp[j] 需要加上 dp[j-nums[i]] 这一部分。(2)不选择当前物品nums[i]前面物品已经能够装满 j 的方案数-dp[j](上一循环的)因此最终 dp[j] 就等于“不选当前物品的就能装满j的方案数”加上“选择当前物品能装满j的方案数”。3.初始化方式只需dp[0]1其余为0方便后面容量进行递推例有一个数字1容量为1所以有一种方法按照递推公式dp[1]dp[0]所以需要dp[0]1否则dp所有元素都是0了。4.遍历顺序和0-1背包问题一样为了避免重复选取物品和能够放入多个物品需要先物品后背包倒序遍历class Solution { public: int findTargetSumWays(vectorint nums, int target) { int sum 0; for(int i:nums) sumi; if (abs(target) sum) return 0; if((sumtarget) % 2 !0) return 0; int rongliang (sumtarget)/2; vectorint dp(rongliang1,0); dp[0]1; for(int i0;inums.size();i){ for(int jrongliang;jnums[i];j--){ dp[j] dp[j-nums[i]]; } } return dp[rongliang]; } };474.一和零