每当我查看计算机竞赛的解决方案时，总会看到“动态规划”一词。我用 Google 搜索了这个术语并阅读了几篇文章，但没有一篇提供编程 VS “动态”编程的简单示例。那么“动态”编程与“普通”编程有何不同呢？ (请使用简单的术语!)
最佳答案
Dynamic Programming在与 Linear Programming 一起使用的意义上更多地使用编程 -- 一种解决问题的机制。
我最近读到的一篇描述(但记不起来源——[需要引用])表明通常的方法是 divide and conquer用于 recursion是一种自上而下的解决问题的方法，而动态规划是一种自下而上的解决问题的方法。
维基百科文章建议计算 Fibonocci sequence是动态规划的绝佳使用——你memoize计算结果以在算法中进一步使用，以避免重新计算类似的结果。
Knuth's algorithm for line-breaking paragraphs是动态规划的另一个很好的例子:如果你考虑在每个单词之间插入换行符的可能性(甚至在 inside 单词中，在连字点处换行)，感觉就像唯一的算法将是指数级的 - - 或者更糟。但是，通过跟踪与先前换行相关联的“坏处”，Knuth 的算法实际上以输入大小的线性时间 运行。 (我必须承认我并不完全理解 Knuth 的算法——只是它非常聪明。)
关于algorithm - "dynamic"编程与 "normal"编程有何不同？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9491097/