动态规划dp

一.概念：动态规划dp：是一种分阶段求解决策问题的数学思想。

　　　　总结起来就一句话：大事化小，小事化了

二.例子

　　1.走台阶问题

F(10):10级台阶的走法数量

所以：F(10)=F(9)+F(8)　　　　　　　　F(9)=F(8)+F(7),F(8)=F(7)+F(6) .......

　　我们把一个复杂的问题分阶段进行简化，逐步简化成简单的问题。这就是动态规划的思想。

当只有一级台阶和两级台阶的时候，走法为1和2.

由此归纳出公式：

　　F(1)=1

　　F(2)=2

　　F(n)=F(n-1)+F(n-2) (n>=3)

动态规划当中包含三个重要的概念：

状态(最优子结构)，状态转移方程，边界

求解决策问题的方法：

　　1.递归

二叉树的高度为N，所以二叉树的节点个数为：2的N-1次方，所以方法的实践复杂度接近O(2^N)

　　2.备忘录算法

从F(1)到F(N)一共有N个不同的输入，在哈希表里存了N-2个结果，所以时间复杂度和空间复杂度都是O(N)

　　3.动态规划dp

自底向上，用迭代的方式推导出结果

时间复杂度是O(N)，由于只引进了两个或三个变量，所以空间复杂度只有O(1)