问题描述

动态规划(DP)算法求出一个问题的所有解

具体问题是：
假设有一个楼梯共有N步，你每次可以爬1步或2步。请编写一个函数来计算，有多少种不同的方法可以爬到顶。
此题给出的解如下：

 int climbStaris(int n){
    if(n <= 1) return 1;
    if(n == 2) return 2;

    int p = 1, q = 2, curr;
    for( int i = 3; i <= n; ++i){
        curr = p + q;
        p = q;
        q = curr;
    }
    return curr;
}

我不是很懂这个for循环意思，为什么进行了这样的循环操作，就能得到这道题的所有解？这里面用到了动态规划吗，哪里体现出来了。

解决方案

如果有1层，那么有1种走法（p）
如果有2层，那么有2种走法（q）
如果有3层，有2个分支，一个先到1层，再到3层，一个是先到2层再到3层，所以是curr = p + q
我们让p始终表示i - 2层，q始终表示i - 1层
因此新的p就是原来的q，新的q就是原来的curr
因此可以知道，对于第i层，肯定是第n-2的方法数（p）+到第n-1的方法数（q）

这个算法无非就是把递归强行写成循环，没什么动态规划。

解决方案二：

因此可以知道，对于第i层，肯定是第n-2的方法数（p）+到第n-1的方法数（q）
->
因此可以知道，对于第i层，肯定是第i-2的方法数（p）+到第i-1的方法数（q）