“动态规划”和“普通”编程有什么不同？

Question

每当我看到计算机竞赛的解决方案时，总是会看到“动态规划”这个术语。我谷歌搜索了这个术语并阅读了几篇文章，但它们都没有提供编程与“动态规划”的简单例子。那么，“动态规划”与“普通”编程有什么不同呢？（请用简单的术语解释！）

- Leo Jiang

---

动态规划实际上可以有几种不同的含义。 - SLaks

可能是[什么是动态规划？]的重复问题(https://dev59.com/L3NA5IYBdhLWcg3wKam3) - DNA

请参阅https://dev59.com/1nI_5IYBdhLWcg3wEOvq（以及其他许多）。 - DNA

Answer 1

动态规划更多地使用了与线性规划中使用的意义相同的“规划”--一种解决问题的机制。

我最近阅读的一篇描述（但现在无法记起来源--[需要引用]）建议，通常在递归中使用的分治方法是自上而下解决问题的方法，而动态规划则是自下而上解决问题的方法。

维基百科文章建议计算斐波那契数列是动态规划的一个很好的应用--您可以在计算它们时记忆化结果以供算法进一步使用，以避免重新计算类似的结果。

Knuth的段落断行算法是另一个动态规划的好例子：如果您考虑在每个单词之间插入换行符（甚至在连字符处分割单词），那么感觉唯一的算法将是指数级别或更糟。然而，通过跟踪与前面的断行相关的“不良因素”，Knuth的算法实际上以输入大小的线性时间运行。（我必须承认我并不完全理解Knuth的算法——只知道它非常聪明。）

- sarnold

Answer 2

你所说的“普通”编程指的是C++/Java/C#编程，对吗？

动态规划并不是那种“编程”。它并不是关于编写代码的，而是在解决复杂问题时将其分解成更简单的问题。这里使用“规划”一词，是指通过将问题分解成更小的子问题来实现。

- CodeBlue

---

这与分治算法编程类似吗？ - Faizan

Answer 3

我知道这是一个旧帖子，但我也有同样的问题，所以我在这里给自己回答。

动态规划有两个特性：

1. 最优子结构：通过将局部子问题的最优解组合起来，可以找到全局最优解。例如，fib(x) = fib(x - 1) + fib(x – 2)
2. 重叠子问题：找到最优解涉及多次求解相同的问题。例如，在斐波那契数列中多次计算fib(x)

根据上述定义/特性，某些问题如“元素是否属于集合？”或“如何求一组数的和？”是否可以被归类为动态规划并不清楚？我可以将集合划分为子集（全局求解）然后求和（获得全局答案）。而且，在子集内部，我多次进行了求和。

我在一本书中找到了一段话，我认为它提供了区分“动态规划”（DP）和“分治算法”（D&C）的非常有用的提示。

1. 在分治算法中，子问题的规模要比原问题小得多。相比之下，动态规划涉及解决的问题只比原问题略微小一些。例如，计算Fib(19)与计算Fib(20)相比并没有太大的差别。而计算十个元素的总和则远远小于计算一千万个元素的总和。

2. 分治算法的效率不依赖于将算法结构化以重复解决相同的问题。相比之下，只有当不同子问题的数量显著小于总子问题数时，动态规划才是有效的。

- Ying

Answer 4

动态规划并不是真正的“编程”，而是表格查找[和存储] - 这就是为了牺牲一点空间来提高时间复杂度[相当多]。

- Fakrudeen