每当我看到计算机竞赛的解决方案时，我总是会看到术语"动态编程"。我在谷歌上搜索了这个词，读了几篇文章，但没有一篇文章提供编程VS"动态"编程的简单例子。那么，"动态"编程与"正常"编程有何不同？（请用简单的术语！）
动态编程更多地使用编程与线性规划（一种解决问题的机制）一起使用。
我最近读到的一篇描述（但已经记不起出处了——[需要引用]）表明，递归中常用的分而治之方法是自上而下的解决问题的方法，而动态编程是自下而上的解决问题方法。
维基百科的文章建议，计算Fibonocci序列是动态编程的一个很好的用途——你可以在计算结果时将其记忆起来，以便在算法中进一步使用，以避免重新计算类似的结果。
Knuth的换行段落算法是动态编程的另一个很好的例子：如果你考虑在每个单词之间插入换行符的可能性（甚至在单词内部的连字符点换行），感觉只有指数算法——甚至更糟。然而，通过跟踪与先前换行相关的"坏"，Knuth的算法实际上在线性时间中随着输入的大小而运行。（我必须承认，我并不完全理解Knuth的算法——只是它非常聪明。）
我认为"正常"编程是指C++/Java/C#编程，对吧？
动态编程不是那种意义上的"编程"。它不是关于编写代码，而是"编程"一词用于通过将复杂问题分解为更简单的问题来解决复杂问题。
动态编程不是真正的"编程"，而是表查找[和存储]-这就是牺牲一点空间来提高时间复杂性[相当多]。
我知道这是一篇旧帖子，但我也有同样的问题，所以我在这里回答自己。
动态编程有两个特性：
- 最优子结构：通过组合局部子问题的最优解，可以找到全局最优解。例如，fib（x）=fib（x-1）+fib（x-2）
- 重叠子问题：找到最佳解决方案涉及多次解决同一问题。例如，在Fibonocci序列中多次计算fib（x）
根据上面的定义/属性，不清楚诸如"元素是否属于集合"之类的某些问题是否存在？或者"如何求集合的和"可以归类为动态规划？我可以将集合划分为子集（全局求解）并将其相加（得到全局答案）。此外，在子集中，我做了多次求和。
我在一本书中找到了一段话，我认为它提供了非常有用的技巧来区分"动态编程"（DP）和"分治算法"（D&C）。
-
在D&C子问题，它们比原始问题小得多。相比之下，DP涉及到解决的问题只比原始问题小一点。例如，计算Fib（19）并不是一个比计算Fibre（20）小得多的问题。而计算十个元素之和要比计算一千万元素之和小得多。
-
D&C算法不依赖于构造算法，从而重复解决相同的问题。相反，只有当不同子问题的数量明显小于子问题的总数时，DP才是有效的。