本文主要是介绍代码随想录冲冲冲 Day36 动态规划Part4，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
又一次越来越感受到了动规的“魅力”，头发又开始掉了
1049. 最后一块石头的重量 II
1.dp数组
dp[j]中的 j是 背包为j的情况下 最多能背的石头的最大量
2.dp数组初始化
首先dp[j]中j表示的是容量 那么这个容量最大值就是所有石头的总重量
因为提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以最大重量就是30 * 1000
这道题的这剩下的最后一个石头，其实就是（总重量 - 一半的重量）- 剩下一半的重量，由于一半的重量是由总重量/2得到的 所以得到的值一定是大于一半重量的，进行相减也就是最后石头的重量
既然target是最大重量的一半，所以dp数组开到15000大小就可以了
3.递推公式
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
这道题对应到01背包问题中的价值恰好就行石头的重量
4.遍历顺序
第一层是每个石头，正序
第二层是背包的容量，倒序
494. 目标和
假设加法的总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = target
x = (target + sum) / 2
里面包括几种情况
·如果目标和大于总和 ---》无解
·如果(target + sum)%2 == 1 --》无解
1.dp数组含义
dp[j] 和为j是 最多有dp[j]种方法
2.初始化dp[0] = 1；
因为我们现在的dp size其实就是相加得所有数 那么相加等于0的情况只有1种
3.递推公式
不考虑nums[i]的情况下，填满容量为j的背包，有dp[j]种方法。
那么考虑nums[i]的话（只要搞到nums[i]），凑成dp[j]就有dp[j - nums[i]] 种方法。
例如：dp[j]，j 为5，
- 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 dp[5]。
- 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 dp[5]。
- 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 dp[5]
- 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 dp[5]
- 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 dp[5]
那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。
dp[j] += dp[j - nums[i]]
4.遍历顺序
第一层 数字的个数 正序
第二层 为Target 倒序
474. 一和零
两个维度的01背包问题
1.dp数组
dp[i][j]: 代表的是一个子集的大小 特性为i个0 和j个1
2.初始化
dp[0][0] 为0 也就是i = 0 j = 0时的最大值
3.递推公式
首先对于每一个str都要统计其中有多少 0和1
dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
然后我们在遍历的过程中，取dp[i][j]的最大值。
所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
可以理解成value是1 然后cost有两个维度 0的数量和1的数量
4.遍历顺序
依然是先遍历物品 也就是每个str
在比那里容量 只不过这时容量有两个维度 0 的数量和1的数量 所以有两个loop
这篇关于代码随想录冲冲冲 Day36 动态规划Part4的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
