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

我正在寻找一个易于理解的例子，有人谁想要学习动态编程。这里有一些关于什么是动态编程的好答案.斐波那契数列就是一个很好的例子，但是它太小了，不足以划破表面。虽然我还没有上过算法课，但它看起来是一个值得学习的好主题，希望它在我春天的清单上。

92458 次浏览
小开

Calculating Levenshtein distances was one of the first problems I solved with dynamic programming; I think it is a decent next step from the Fibonacci sequence in terms of complexity.

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

小开

Check out this site: Dynamic Programming Practice Problems

小开

The idea behind dynamic programming is that you're caching (memoizing) solutions to subproblems, though I think there's more to it than that.

There are many Google Code Jam problems such that solutions require dynamic programming to be efficient. Examples:

Welcome to Code Jam (moderate)

Cheating a Boolean Tree (moderate)

PermRLE (hard)

Note that each of the Code Jam practice contests has a "Contest Analysis" section for if you're stumped trying to solve the problem.

小开
  1. Geeks for geeks has a great collection of dynamic programming problems. I feel this set is one of the best if you are preparing for interview.
  2. If you want small tutorial videos on DP problems you can check this problem set from MIT.
小开

Here is a good tutorial comprising 29 solved DP problem with great explanation.


提交答案