代码随想录算法训练营|day43

第九章 动态规划 01背包

• 1049.最后一块石头的重量II
• 494.目标和
• 474.一和零
• 代码随想录文章详解
• index.php/tags-41973.html" >���结

  1049.最后一块石头的重量II

  每次选出的两块石头重量越接近，最后剩余的重量越轻

  （）

  将石头分成两堆，寻找重量轻的那一堆石头的最大值maxWeight，则另一堆石头重量为sum-maxWeight，最终结果为sum-2*maxWeight，因此定义背包容量target = sum(nums)/2

  dp[i]表示背包容量为i时，能装到的最大石头重量。

  （）

  func lastStoneWeightII(stones []int) int {sum := 0for _, stone := range stones {sum += stone}target := sum / 2dp := make([]int, target+1)for _, stone := range stones {for i := target; i >= stone; i-- {dp[i] = max(dp[i], dp[i-stone]+stone)}}return sum - 2*dp[target]}

  494.目标和

  假设组成的等式中被减数为left，减数为right，和为sum，题意为寻找满足left-right=target的个数，改写成left-(sum-left)=target，即为寻找数组中满足left=(sum+target)/2的个数。

  dp[i]表示背包容量为i时，有dp[i]种方法能装满背包。若abs(target)或被减数为小数，无解

  func findTargetSumWays(nums []int, target int) int {sum := 0for _, num := range nums {sum += num}if abs(sum) = num; i-- {dp[i] += dp[i-num]}}return dp[left]}func abs(x int) int {return int(math.Abs(float64(x)))}

  474.一和零

  dp[i][j]表示背包容量为i，j时，能用str装满背包的个数，即strs子集的个数

  func findMaxForm(strs []string, m int, n int) int {dp := make([][]int, m + 1)for i := 0; i = zeros; i-- {for j := n; j >= ones; j-- {dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1)}}}return dp[m][n]}func countZerosAndOnes(str string) []int {count := make([]int, 2)for _, c := range str {count[c-'0']++}return count}

  代码随想录文章详解

  1049.最后一块石头的重量II

  494.目标和

  474.一和零

  总结

  求装满背包有几种方法的情况下，递推公式一般为：dp[j] += dp[j - nums[i]]

  没得选和可选可不选