C语言中什么是DP思想

Python023

C语言中什么是DP思想,第1张

1、DP是dynamic programming的缩写，中文为动态规划编程，是一种编程思想，算法里面要学到的。和编程语言没有关系。

2、动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。用一个表来记录所有已经解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划的基本思想。

DP就是动态规划（Dynamic Programming)。

1，什么是动态规划（DP）？

非常重要！，不要认为概念不重要，理解的深刻，你才知道对于什么样的问题去考虑有没有动态规划的方法，以及如何去使用动态规划。

1）动态规划是运筹学中用于求解决策过程中的最优化数学方法。 当然，我们在这里关注的是作为一种算法设计技术，作为一种使用多阶段决策过程最优的通用方法。

它是应用数学中用于解决某类最优化问题的重要工具。

2）如果问题是由交叠的子问题所构成，我们就可以用动态规划技术来解决它，一般来说，这样的子问题出现在对给定问题求解的递推关系中，这个递推关系包含了相

同问题的更小子问题的解。动态规划法建议，与其对交叠子问题一次又一次的求解，不如把每个较小子问题只求解一次并把结果记录在表中（动态规划也是空间换时间

的），这样就可以从表中得到原始问题的解。

关键词：

它往往是解决最优化问题滴

问题可以表现为多阶段决策（去网上查查什么是多阶段决策！）

交叠子问题：什么是交叠子问题，最有子结构性质。

动态规划的思想是什么：记忆，空间换时间，不重复求解，由交叠子问题从较小问题解逐步决策，构造较大问题的解。

一个最简单的DP问题就是斐波拉切数列。f(n) = f(n-1) + f(n-2)

如果采用递归的方法计算，复杂度很高的。

还有一个问题就是矩阵的连乘问题， 计算最少的乘法次数，这些都是经典的DP问题。