目录

1049.最后一块石头的重量

 思路

代码

494.目标和

思路

代码

 474.一和零

思路

代码

视频讲解：动态规划之背包问题，这个背包最多能装多少？LeetCode：1049.最后一块石头的重量II_哔哩哔哩_bilibili

代码随想录

        一开始我根本就看不懂，真的看着同班的学霸算法课考试框框写完，帅气提交离场都给我看傻了，分分钟就能写出来提交真的牛掰。这道题没思路说明你和我一样没有悟到他的本质：本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

        这一下就明朗的啊，和昨天的分割等和子集不是一样吗，背包的容量就是总容量的一半。

        放上Carl哥的动态规划五部曲

1.确定dp数组以及下标的含义

        dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。

        可以回忆一下01背包中，dp[j]的含义，容量为j的背包，最多可以装的价值为 dp[j]。

相对于 01背包，本题中，石头的重量是 stones[i]，石头的价值也是 stones[i] ，可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]”

2.确定递推公式

        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]的含义。

3.dp数组如何初始化

        既然 dp[j]中的j表示容量，那么最大容量（重量）是多少呢，就是所有石头的重量和。

因为提示中给出1 = nums[i - 1]: dp[i][j] += dp[i - 1][j - nums[i - 1]] # 选取当前元素 return dp[len(nums)][target_sum] # 返回达到目标和的方案数  474.一和零 通过这道题目，大家先粗略了解， 01背包，完全背包，多重背包的区别，不过不用细扣，因为后面 对于 完全背包，多重背包 还有单独讲解。

视频讲解：动态规划之背包问题，装满这个背包最多用多少个物品？| LeetCode：474.一和零_哔哩哔哩_bilibili

代码随想录

        大家学算法要坚持学，能坚持就要尽量坚持，我之前因为期末拉下了太多天没刷，结果今天要算法期末考试了想着算道练练手结果一点都不会写了。。。

        这道题是多重背包的类型题，之前蓝桥杯学的又忘了。。。（每日崩溃1/1）其实代码和01背包差不多，就是把内层遍历背包容量的顺序变成从前向后遍历，其他都差不多的。