文章目录
- 1049. 最后一块石头的重量 II
- 思路
- 思路代码
- 官方题解
- 困难
- 494.目标和
- 思路
- 思路代码
- 困难
- 474.一和零
- 思路
- 思路代码
- 困难
- 今日收获
1049. 最后一块石头的重量 II
1049.最后一块石头的重量 II
思路
和分割等和子集一样，除2作为背包容量。
思路代码
func lastStoneWeightII(stones []int) int {sum:=0for _,v:=range stones{sum+=v}target:=sum/2dp:=make([]int,target+1)for i:=0;i<len(stones);i++{for j:=target;j>=stones[i];j--{dp[j]=max(dp[j-stones[i]]+stones[i],dp[j])}}return sum-2*dp[target]}func max(i,j int) int{if i<j{return j}return i
}
官方题解
本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。
是不是感觉和昨天讲解的416. 分割等和子集 (opens new window)非常像了。
本题物品的重量为stones[i]，物品的价值也为stones[i]。
对应着01背包里的物品重量weight[i]和 物品价值value[i]。
接下来进行动规五步曲：
确定dp数组以及下标的含义
dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。
可以回忆一下01背包中，dp[j]的含义，容量为j的背包，最多可以装的价值为 dp[j]。
相对于 01背包，本题中，石头的重量是 stones[i]，石头的价值也是 stones[i] ，可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]”
确定递推公式
01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题则是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
一些同学可能看到这dp[j - stones[i]] + stones[i]中 又有- stones[i] 又有+stones[i]，看着有点晕乎。
大家可以再去看 dp[j]的含义。
确定遍历顺序
在动态规划：关于01背包问题，你该了解这些！（滚动数组） (opens new window)中就已经说明：如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！
困难
将总重量除2得到背包容量，最后两堆相减得到最小背包值：
(sum-dp[target]) - dp[target]
494.目标和
494.目标和
思路
2*背包容量-sum=target
注意target<0的话，取反，不影响方案个数。
思路代码
func findTargetSumWays(nums []int, target int) int {sum:=0if target<0{target=(-target)}for _,v:=range nums{sum+=v}if (sum+target)%2!=0{return 0}capacity:=(sum+target)/2dp:=make([]int,capacity+1)dp[0]=1for i:=0;i<len(nums);i++{for j:=capacity;j>=nums[i];j--{dp[j]=dp[j]+dp[j-nums[i]]}}return dp[capacity]}func max(i,j int)int{if i<j{return j}return i
}
困难
target<0的话注意取反，取反后方便计算，并且不影响方案的个数，只是方案的正负号是反的罢了。
474.一和零
474.一和零
思路
两个维度的0-1背包
思路代码
func findMaxForm(strs []string, m int, n int) int {dp:=make([][]int,m+1)for k,_:=range dp{dp[k]=make([]int,n+1)}for k:=0;k<len(strs);k++{count0:=0count1:=0for _,c:=range strs[k]{if c=='0'{count0++}else{count1++}}for i:=m;i>=count0;i--{for j:=n;j>=count1;j--{dp[i][j]=max(dp[i][j],dp[i-count0][j-count1]+1)}}}return dp[m][n]
}func max(i,j int)int{if i<j{return j}return i
}
困难
要想到这是0-1背包，由于有m和n，所以有两个维度。
今日收获
0-1背包可以解决分割问题，方案个数，背包内个数，背包内价值最大值等等问题，对应不同的dp递推公式，但循环都是一样的。
外层循环物品，内层循环容量，内层注意倒序遍历。比如分割问题，容量可能就是值的和，但是循环仍然是一样的处理。
外层循环处理的是当前元素放入或者不放入的状态；
内层循环处理的是背包容量的值，每一个容量值需要对应到外层循环的当前物品，去判断上一层，也就是放入当前物品时，上一层的容量就需要减去当前物品的状态。
注意外层循环遍历到某一层的时候是，背包内状态是判断前i个物品的状态。
本文链接：https://my.lmcjl.com/post/1229.html
4 评论