16｜课程回顾与总结（下）
卢誉声
你好，我是卢誉声。今天我们来继续课程总结，重点回顾几类经典的动态规划问题，并尝试使用我们的解题框架去解决它们。这几类问题我们前面都详细讲过，再带你巩固一遍。
经典的动态规划问题
动态规划的问题主要分为三类：
求最优解（最大值和最小值）：从一系列方案中寻找最优解决方案；
求方案总数：计算满足要求的解决方案的数量；
求可行性（True 或 False）：确定提出的问题是否存在可行方案。
下面我们分别来看看这几类问题的代表性问题。
1. 背包问题
首先我们来看下背包问题，背包问题是一类非常经典的最优化问题，一般都是希望得到背包可以容纳的最大物品价值，是求最优解的问题代表。
背包问题有很多类，常见的背包问题有 0-1 背包、完全背包、多重背包等，再多就是在这些问题上的变种和延伸。但是无论是什么问题，基本都逃不过一个标准的题目描述模板。
问题：给你一个可放总重量为 W 的背包和 N 个物品，对每个物品，有重量 w 、价值 v 和数量 3 个属性，那么第 i 个物品的重量为 w[i]，价值为 v[i]，数量为 k[i]（k≥1）。现在让你用这个背包装物品，问这个背包最多能装的价值是多少？
让我们来将几类背包问题对号入座，套入这个模板里面。
首先是 0-1 背包，所谓 0-1 背包就是每个物品最多只能选择 1 个，所以要不选择 0 个，要不选择 1 个，因此我们称之为 0-1 背包。所以 0-1 背包也就是说所有物品的数量 k[i] 都为 1。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入介绍了动态规划问题中的经典背包问题，包括0-1背包、完全背包和多重背包，以及路径问题、跳跃游戏问题、子数组问题和子序列问题。作者详细讲解了这些问题的解题思路、状态转移方程以及Java和C++的实现代码。此外，文章还总结了动态规划的优化方法，包括减少状态总数、减少每个状态转移的状态数和减少每次状态转移的时间，以及空间复杂度的优化技巧如滚动数组。总的来说，本文内容详实，适合对动态规划感兴趣的读者阅读学习。通过对动态规划问题的总结，读者可以快速了解各种问题的解题思路和实现方法，为进一步深入学习和实践打下良好基础。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《动态规划面试宝典》，新⼈⾸单¥59
《动态规划面试宝典》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(2)
- 最新
- 精选
- 我是一把火老师，多重背包的实现代码中的 int maxK = Math.max(k[tn], rw / w[tn])，是否应该改为Math.min(k[tn], rw / w[tn]) ？也就是取两者中较小的那一个。因为要考虑到此时背包剩余容量最多能容纳n件当前物品，但实际上当前物品的个数少于n件 或者 当前物品有n件，但剩余容量不足以容纳n件。
作者回复: 的确应该是min，问题已修改。
2020-11-0523 
帽子狗真就是前面留言多后面留言少啊... 说实话，这套课程对我解 DP的套路没有太大提升，因为之前就刷了很多 DP题了。 但是老师能系统的总结出动态规划的特性，已经对自顶而下和自底而上的逻辑梳理，让我能更科学地看待DP问题。 不过要对DP信手拈来还是得多刷，套路掌握了，灵感也是必不可少的。作者回复: 嗯嗯，上手练习是很有必要的。
2020-11-122
收起评论
