教学楼的楼梯递归求解+动态规划求解

首先读题:

        假设共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

解题思路: 

        假设共有M级，所在位置为Z级，共有N种走法 需要跨过的台阶数量为M-Z   由题意Z=1，每次只能+1或+2，当Z=M时走完全程：

                                        则有：

                                                 M=1时   M-Z=0（不需要向上）          位置不变                                                                            N=1

                                                 M=2时   M-Z=1（需要向上一级）       只能向上跨一级     Z+1=M                                                N=1

                                                 M=3时   M-Z=2（需要向上二级）       有且只有二种走法     Z+1+1=M或Z+2=M                        N=2

                                                 M=4时   可先跨一级，此时Z=2，M-Z=2，则下一步有二种走法    Z+1+1=M或Z+2=M     N1=2

                                                               或先向上二级，此时Z=3，M-Z=1，则下一步有一种走法    Z+1=M     N2=1                  N=N1+N2=3

                                                 以此类推:

                                        即每踏上新的一级，当（剩余台阶数量）M-Z<=1时，仅对于下一步来说，有一种走法，否则有两种走法。

 定义函数如下

int zf(int m){
    if(m<=2){    //即M-Z<=1
        return 1;   
    }else{
        return zf(m-1)+zf(m-2);
    }
}

动态规划:

    设f(x)表示爬到第x级台阶的方案数,以逆向思维来看,最后一步可能跨越了1级,也可能跨越了两级.

                      则:            f(x)=f(x−1)+f(x−2)

即:爬到第x级台阶的走法是爬到第x-1级和第x-2级的走法数的和;

其中f(1)=1        f(2)=1        f(3)=f(1)+f(2)=2        f(4)=f(2)+f(3)=3

定义函数如下:

int zf(int m){
    int x=0,y=1,r=0;
    for(int i=1;i<m;i++){
    r=x+y;
    x=y;
    y=r;
    }
    return r;
}