动态规划面试宝典
卢誉声
Autodesk 首席工程师
9629 人已学习
新⼈⾸单¥59
登录后,你可以任选2讲全文学习
课程目录
已完结/共 23 讲
动态规划面试宝典
15
15
1.0x
00:00/00:00
登录|注册

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
立即购买
登录 后留言

全部留言(2)

  • 最新
  • 精选
  • 我是一把火
    老师,多重背包的实现代码中的 int maxK = Math.max(k[tn], rw / w[tn]),是否应该改为Math.min(k[tn], rw / w[tn]) ?也就是取两者中较小的那一个。因为要考虑到此时背包剩余容量最多能容纳n件当前物品,但实际上当前物品的个数少于n件 或者 当前物品有n件,但剩余容量不足以容纳n件。

    作者回复: 的确应该是min,问题已修改。

    2020-11-05
    2
    3
  • 帽子狗
    真就是前面留言多后面留言少啊... 说实话,这套课程对我解 DP的套路没有太大提升,因为之前就刷了很多 DP题了。 但是老师能系统的总结出动态规划的特性,已经对自顶而下和自底而上的逻辑梳理,让我能更科学地看待DP问题。 不过要对DP信手拈来还是得多刷,套路掌握了,灵感也是必不可少的。

    作者回复: 嗯嗯,上手练习是很有必要的。

    2020-11-12
    2
收起评论
显示
设置
留言
2
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部