想要了解动态编程的人的一个简单示例

Question

我正在寻找一个想要学习动态编程的人可以理解的例子。 There are nice answers here about what is dynamic programming。斐波纳契序列是一个很好的例子，但它太小而不能划伤表面。虽然我还没有选择算法类，但它似乎是一个很好的学习主题，希望它在我的春天名单上。

Answer 1

计算Levenshtein距离是我用动态规划解决的第一个问题之一;我认为就复杂性而言，这是斐波纳契序列的下一步。

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

Answer 2

看看这个网站：Dynamic Programming Practice Problems

Answer 3

背后动态规划的想法是，你缓存（memoizing）解决方案的子问题，但我认为还有更给它比。

有很多Google Code Jam问题，例如解决方案需要动态编程才能高效。例子：

Welcome to Code Jam (moderate)

Cheating a Boolean Tree (moderate)

PermRLE (hard)

注意，每个代码果酱实践竞赛的有，如果你难倒试图解决的问题“比赛分析”一节。

Answer 4

1. 极客极客有很大的动态规划问题collection。如果你正在准备面试，我觉得这套是最好的。
2. 如果您想要关于DP问题的小教程视频，您可以检查MIT的问题集this。

Answer 5

Here is a good tutorial包含29个解决DP问题的很好解释。