动态规划的一点小思考
基本思想
动态规划是在算法设计中求解最优解的一种思想，这种思想很强大，可以解决许许多多在ACM中遇到的最优值求解的问题上面，但同时这种思想也不是一朝一夕就能深入领会的，对初学者而言它晦涩难懂（牛人请绕路），对用惯了动态规划的人而言，它又是那么得顺手和习惯。我本人是自学动态规划的，虽然没有什么高深的理论基础，只是想把自己的一点对动态规划的思考写下来，让初学者也能有所启迪，让我自己也能回顾回顾。
动态规划可以说是一种递归解的优化，是在空间复杂度和时间复杂度上的优化。简单来说，动态规划需要满足下面3个条件：
第一：题目中存在子问题
第二：题目中的子问题有部分是重叠的
第三：子问题可以通过递推公式推导出下一个子问题的解
递推公式，想必很多人都在中学中学过，最经典的例子是斐波那契数列，它的递推公式是
F(0) = 0
F(1) = 1
F(N) = F(N-1) + F(N-2) 当N>1
动态规划中也会用到递推公式，下面我就那一个最经典的例子来说明一下
有N个台阶，每一次你只能跨1节台阶或者2节台阶上楼，请问N=50的时候你上楼有几种走法？
题目很容易理解，其实就是求50级台阶的上楼方法数，但是这个问题如何才能解决呢？新手拿到这道题的时候不知所措，其实我们只要仔细想想会发现，它其实是存在子问题的。请思考如下问题：
请问：如果你知道了1节台阶和2节台阶有几种走法，你可否推导出3节台阶有几种走法？
请问：如果你知道了2节台阶和3节台阶有几种走法，你可否推导出4节台阶有几种走法？
请问：如果你知道了3节台阶和4节台阶有几种走法，你可否推导出5节台阶有几种走法？
……
请问：如果你知道了n-1节台阶和n-2节台阶有几种走法，你可否推导出n节台阶有几种走法？
请读者先自己仔细思考一下，再往下看。
我们发现n节台阶的问题是可以转化为n-1和n-2节台阶的走法的，因为最后一步一定是要么从n-1节走到n节，要么从n-2节走到n节，其他再无可能，于是我们分别讨论这两种情况：
第一种情况，从n-1节走到n节，假定我我们已经在n-1节台阶上面了且已知n-1节台阶的走法数是W，那么我们只要再走1节台阶就到达了n节台阶，所以这种走法的方法数是W。
第二种情况，从n-2节走到n节，假定我们已经在n-2节台阶上面了且已知n-2节台阶的走法数是S，这时我们可以有2种走法，第一是一次走1步，共2步走到n节，第二是一次走2步，共走1步走到n节，但由于第一种方法会走到n-1节，这种走法第一种情下我们已经讨论过了，所以这里第二种情况的走法数是S。
于是我们得到，走到n节台阶的走法总共有W+S种（走到n-1节和走到n-2节的走法数之和）。
在这里n、W、S都是字母，它适用于所有情况，于是我们就可以得到递归式：
n节台阶的走法 = n-1节台阶的走法 + n-2节台阶的走法
而1节台阶和2节台阶的走法我们是已知的，所以可以得到50节台阶的走法
所以这道题其实就是求解稍加变化后的斐波那契数列F(N)
F[1] = 1;
F[2] = 2;
F[N] = F[N-1] + F[N-2];
代码如下(Java)
int count(int n){
int[] dp = new int[n+1];
dp [1] = 1;
dp[2] = 2;
for(int i=3;i<=n;i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
使用动态规划，一般的思路是找到递归公式，并将每一步的解保存下来以供计算后面的解使用，最终从子问题递归地得到最终问题的答案。
