算法复习-动态规划 （1）

原理

问题的最优解如果可以由子问题的最优解推到得到，则可以先求解子问题的最优解，再构造原问题的最优解；若子问题由较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。

特点

• 将原始问题划分为一系列子问题
• 求解每一个子问题仅一次，并将结果保存在一张表中，以后用到直接存取，不需要重复计算
• 整体问题的最优解取决于子问题的最优解（状态转移方程，即将子问题称为状态，最终状态的求解归结于其他状态的求解）

设计步骤

1. 递归+记忆化 —> 递推
2. 找到状态变量并定义
3. 寻找状态转移方程
4. 分析分解条件
5. 优化子结构

   例题讲解

   讲解动态规划这个算法没有什么例子斐波拉契数列更经典的了。后面大部分的动态规划题目都是以斐波拉契数列为基础展开的。
   题目：
   1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…
   请求出第n个数

   回溯法(递归)

   很明显的，从第三个数字开始，后面每个数字的值都是前两个数字相加得到的，那么我们可以写出一个很简单的递归程序.

   int Solution(int n)
   {
   	if(n<=1)
   		return 1;
   	return Solution(n-1)+Solution(n-2);
   }

   我们可以写的更简单一点，一句话就够了

   return n<=1?1:Solution(n-1)+Solution(n-2);

   这样写下来是不是逼格高了很多，我们将这个程序的函数调用过程画出来就是这样：

图中以n=5为例，那么如果n趋向于无穷大，整个算法的时间复杂度就是趋向于2的n次方（用VC6.0跑太大数字直接就崩溃了23333）。
实际上，这个回溯法我们可以进一步优化为动态规划的算法。

动态规划

1. 上面的设计步骤中的递归已经想出来了，那么记忆化呢？图中所有没有被绿色标记的地方都重复计算了一次，这对时间的消耗是致命的，我们可以将已经计算出来的结果都用一个数组保存起来（这就是记忆化），这个数组就是学动态规划每个人都知道的一个状态变量dp。
2. 状态变量的定义很快就可以得出：dp[n]表示斐波拉契数列的解。
3. 状态转移方程:f[n]=f[n-1]+f[n-2]
4. 分析分解条件:这一步的时候我们一般要考虑初始值(例如这道题就是输入值为1或2的条件下)和特殊情况。可以得出f[n]=f[n-1]+f[n-2] (n>2).
5. 优化子结构: 和贪心算法不同，动态规划是从全局的角度来考虑最优解的，同时状态变量下存储的都是每个子问题下面的最优解（这里不太理解的后面还有爬梯子的例题）.我们观察状态转移方程，发现实际上用到的就3个变量，分别是f[n]、f[n-1]、f[n-2]，我们可以将数组进一步优化为大小为3的数组。
   最后，代码如下：

   int Solution(int n)
   {
   	int dp[3];
   	if(n<=2)
   		return 1;
   	dp[0]=1;
   	dp[1]=1;
   	for(int i=2;i<n;i++)  
           //从2开始的原因是跳过前两个情况(n=1,n=2)
   	{
   		dp[2]=dp[0]+dp[1];
   		dp[0]=dp[1];
   		dp[1]=dp[2];
   	}
   	return dp[2];
   	
   }