17.18.动态规划，背包问题
没加记事本的模板
加记事本的模板
198. 打家劫舍
思路
dfs(i) 从一共i家偷，最多可以偷多少
不偷第i家，dfs（i）=》dfs(i-1)
偷第i家，dfs（i）=》dfs（i-2）+nums[i]
只回溯，不剪枝
画图
494. 目标和
小技巧
等价
思路
有的数字前面要加 +（我们把它们叫做 正数军团P PP）
有的要加 -（我们把它们叫做 负数军团N NN）
P+N=sum
P-N=target
P+N-（P-N）=2N=sum-target；
所以这题我们可以简化成从nums中挑和为N的组合
这样我们可以用组合型回溯或者0-1背包来解决
0-1背包
dfs（i，c）的含义有2层
微观的：现在就来折腾第i个
宏观的：用i个数，填满c的背包，有几种方法。（记住计算机是从0开始的）
选第i个,dfs(i,c)=>dfs(i-1,c-nums[i])
不选,dfs(i,c)=>dfs（i-1，c）
所以dfs（i，c）= dfs(i-1,c-1) + dfs（i-1，c）
代码
首先写一下0-1背包的代码（不包含剪枝）
classSolution{public:intfindTargetSumWays(vector<int>&nums,inttarget){intn=nums.size();intl=accumulate(nums.begin(),nums.end(),0)-target;if(l<0||l%2!=0){return0;}intm=l/2;autodfs=[&](thisauto&&dfs,inti,intc)->int{if(i<0){returnc==0;}returndfs(i-1,c)+dfs(i-1,c-nums[i]);};//从第0~第n-1个中，装满背包m，有几种方案。returndfs(n-1,m);}};加上记事本，剪枝
classSolution{public:intfindTargetSumWays(vector<int>&nums,inttarget){intsum=accumulate(nums.begin(),nums.end(),0);intl=sum-target;intn=nums.size();if(l%2==1||l<0){return0;}//负数军团 在nums中，挑几个数的和为cintm=l/2;vector<vector<int>>memo(n,vector<int>(m+1,-1));autodfs=[&](thisauto&&dfs,inti,intc)->int{if(i<0){returnc==0?1:0;}// 之前计算过if(memo[i][c]!=-1){returnmemo[i][c];}// 只能不选if(c<nums[i]){returnmemo[i][c]=dfs(i-1,c);}// 不选 + 选returnmemo[i][c]=dfs(i-1,c)+dfs(i-1,c-nums[i]);};returndfs(n-1,m);}};322. 零钱兑换
思路
dfs(i,c) 共i个数据，每个数据可以用无数处，返回填满背包最少需要多少数据
- 不选第i个，
dfs(i,c)变成dfs(i - 1, c) - 选第i个，
dfs(i,c)变成dfs(i, c - coins[i]) + 1（完全背包），如果是01背包则是dfs(i-1, c - coins[i]) + 1
没剪枝
classSolution{public:intcoinChange(vector<int>&coins,intamount){intn=coins.size();autodfs=[&](thisauto&&dfs,inti,intc)->int{if(i<0){//如果 c == 0，说明钱刚好凑齐了！还需要 0 枚。returnc==0?0:INT_MAX/2;}//只能不选if(c<coins[i])returndfs(i-1,c);//不选和选returnmin(dfs(i-1,c),dfs(i,c-coins[i])+1);};intans=dfs(n-1,amount);returnans<INT_MAX/2?ans:-1;}};剪枝
加了
if(memo[i][c]!=-1)returnmemo[i][c];