一个想要了解动态规划的人的简单示例

Question

我正在寻找一个易于理解的例子，以便有人学习动态规划。 这里有关于什么是动态规划的不错的答案。斐波那契数列是一个很好的例子，但它太小了，无法深入了解动态规划。虽然我还没有上过算法课，但它看起来是一个非常值得学习的主题，希望明年春季能在我的计划中。

- Khaled Alshaya

Answer 1

看看这个网站：动态规划练习题

- Nick Dandoulakis

---

通过观看MIT的这个讲座http://video.mit.edu/watch/introduction-to-algorithms-lecture-19-dynamic-programming-i-fibonacci-shortest-paths-14225/，并解决上述问题，将有助于您理解为什么动态规划是有帮助的。 - pg2286

就拿评论中的YouTube链接来说，它已经失效了。新链接：https://www.youtube.com/watch?v=OQ5jsbhAv_M - AJP

看看我找到的这套视频，它直观地介绍了算法的自顶向下和自底向上两个方面：https://www.youtube.com/playlist?list=PLx-Ye3Zw0WL0O_IDmbcVHlKqJuGEfw3VG。 - william007

看起来MIT把他们的内容从主页移到了MIT OpenCourseWare页面，所以@pg2286提供的链接已经失效了。现在的链接是19. 动态规划I。完整的播放列表算法导论也可用。 - rite2hhh

Answer 2

这是一篇不错的教程，其中包含29个解决动态规划问题的方法以及很好的解释。

- akashchandrakar

Answer 3

动态规划的思想是将子问题的解缓存（记忆化），尽管我认为其中还有更多的内容。

有许多Google Code Jam问题需要使用动态规划才能高效地解决。例如： 欢迎来到Code Jam（中等） 作弊布尔树（中等） PermRLE（困难） 请注意，每个Code Jam练习比赛都有一个“竞赛分析”部分，如果您在尝试解决问题时遇到困难，请查看该部分。

- Joey Adams

---

感谢提供这些资源。我时不时地解决一两个项目欧拉问题，但似乎在某些需要动态规划知识的问题上卡住了。 - Khaled Alshaya

Answer 4

1. Geeks for geeks拥有一个很棒的动态规划问题收集。我认为这个系列是准备面试时最好的选择。
2. 如果你想要关于DP问题的短小教程视频，可以查看MIT的这个问题集。

- Diptendu

Answer 5

计算Levenshtein距离是我用动态规划解决的第一个问题之一；我认为它在复杂性方面比斐波那契数列是一个不错的下一步。

http://en.wikipedia.org/wiki/Levenshtein_distance

- David Winslow