第19讲:动态规划 I:斐波那契数列、最短路径
Lecture 19: Dynamic Programming I: Fibonacci, Shortest Paths
频道:MIT OpenCourseWare · 时长:51:47 · 发布:2013-01-14 · 播放:2903120
简介
Erik Demaine 的 MIT 6.006 讲座,通过斐波那契数列和最短路径介绍动态规划。涵盖记忆化、子问题和最优子结构。
HN 为什么推荐
被推荐为来自知名讲师的动态规划清晰入门介绍。
请观看这个 MIT 入门介绍 — HN, 2021
中文字幕节选
以下内容根据知识共享许可协议提供。 您的支持将帮助MIT OpenCourseWare 继续免费提供高质量的教育资源。 如需捐款或查看来自数百门MIT课程的 更多材料,请访问MIT OpenCourseWare,网址为ocw.mit.edu。 教授:我们将开始一个全新且令人兴奋的主题——动态规划。 观众:太棒了!教授:是啊! 太令人兴奋了。实际上,我真的很兴奋,因为动态规划 是我在算法领域最喜欢的东西。 接下来四节课都会讲这个,太令人兴奋了。 它有很多不同的方面。 它是一种非常通用、强大的设计技术。 这门课我们不太讨论算法设计, 但动态规划非常重要。 而且也需要一点时间才能掌握。 我们希望在006这门课里现在就把它灌输给你们。 总的来说,我们的动机是设计 新算法,而动态规划,也叫DP, 是一种很好的方式—— 或者说是一种非常通用、强大的方法。 它特别适合,也是为优化问题 而设计的,比如最短路径问题。 你想找到做某事的最佳方式。 最短路径就是你想找到最短的路径,长度最小的路径。 你想最小化、最大化某些东西,那就是 一个优化问题,通常 解决这类问题的好算法都涉及动态规划。 这个说法有点宽泛。 你也可以把动态规划看作一种穷举搜索。 穷举搜索通常不是好办法,因为它会导致指数级时间。 但如果你通过动态规划巧妙地做, 通常能得到多项式时间。 所以一个观点是,动态规划 大致就是仔细的暴力搜索。 这是一种有趣的组合。 有点矛盾修辞。但我们采用暴力搜索的思想,即 尝试所有可能性,你仔细地做,就能得到多项式时间。 有很多问题,基本上 唯一已知的多项式时间算法就是通过动态规划。 它并不总是有效,有些问题 我们认为不存在多项式时间算法, 但当可能时,DP是一种很好的、 通用的方法。 我们将大量讨论动态规划。 有很多不同的思考方式。 今天我们会看几个。 今天我们先热身,看一些相当简单的问题, 这些我们已经知道如何解决,即计算斐波那契数。 这很容易。还有计算最短路径。 然后在接下来的三节课中,我们会看到更有趣的例子, 这些例子中,你甚至能在多项式时间内解决 问题,这相当令人惊讶。 不过,你脑海中第一个迫切的问题 可能是,为什么叫动态规划? 这到底是什么意思? 我以前有一套说辞,你知道,编程指的是—— 我认为是这个词的英式含义,是关于优化的。 美式英语中的优化有点像英式英语中的编程, 你想设置程序——比如你的火车时刻表之类的, 编程最初就是从这里来的。 但我查了一下动态规划这个名字的真实历史。 动态规划是由一个叫Richard Bellman的人发明的。 你可能在Bellman-Ford算法中听说过Bellman。 所以这实际上是Bellman-Ford的前身。 我们将会看到Bellman-Ford在这种设定下自然地出现。 这里有一段关于他的引述。 它说,Bellman解释说,他发明动态规划这个名字
HN 上的讨论
> 在面试中,他们经常希望你显式地构造数组,即这是录用和强烈录用的区别,正是因为 @lru_cache 更容易 你是认真的吗?真的有人要求你“使用数组”。如果他们真的这么做了,那简直是愚蠢至极。 > 对于真正的生产级实现,使用递归很容易导致栈溢出 递归解决方案并不自动意味着使用方法栈。你可以使用显式栈来实现递归解决方案。 > 请使用正确的动态规划。 没有“正确的”动态规划。请观看这个 MIT 入门讲座 [VIDEO]。 — dominotw, 2021-04
我觉得我从未在面试中被问到过动态规划问题,而且只在编程时用过一次。尽管如此,我喜欢 MIT 关于它的讲座:[VIDEO] — dehrmann, 2021-02
你可能也会喜欢 Erik Demaine 的几节课:动态规划 I:斐波那契、最短路径 [VIDEO] 动态规划 II:文本对齐、二十一点 [LINK] — gbacon, 2019-04
当你处理大型数据集时(例如 Hadoop/Spark……),BigO 开始严重显现影响。动态规划也要求你对它有点概念。参见 [VIDEO] 了解一些很酷的解释。 — philippeback, 2016-08
相关视频
- Cgroups、命名空间及其他:容器由什么构成? · Docker · 54:24
- Satchin Panda 博士谈限时进食及其对肥胖、肌肉质量和心脏健康的影响 · FoundMyFitness · 1:31:34
- Clojure 并发 - Rich Hickey · ClojureTV · 2:32:38
- 高效程序 - Clojure 10年 - Rich Hickey · ClojureTV · 1:14:51
- 是什么让这首歌如此伟大?《Into You》MAX MARTIN · Rick Beato · 30:12
- 林-曼努尔·米兰达在白宫诗歌朗诵会上的表演:(8之8) · The Obama White House · 4:27
- 如何演讲 · MIT OpenCourseWare · 1:03:42
- 1. 人类行为生物学导论 · Stanford · 57:14
- 领导力实验室:有效写作的艺术 · UChicago Social Sciences · 1:21:51
- MIT 的聚变能之路(IAP 2017)- Zach Hartwig · MIT Plasma Science and Fusion Center · 1:11:39
- 斯坦福 Sapolsky 谈美国抑郁症(完整讲座) · Stanford · 52:28
- 公正:该如何做是好?第 01 集“谋杀的道德侧面” · Harvard University · 54:56
- 第一讲 | MIT 18.06 线性代数,2005 年春季 · MIT OpenCourseWare · 39:49
- 兰迪·波许的最后一课:实现你童年的梦想 · Carnegie Mellon University · 1:16:27
- 第一讲A:Lisp概述与简介 · MIT OpenCourseWare · 1:12:55
- 讲座 1A | MIT 6.001 计算机程序的构造和解释,1986 · MIT OpenCourseWare · 1:12:55