递归算法之-爬楼梯

一、爬楼梯算法递归实现：假设一个楼梯有N阶台阶，人每次最多跨M阶，求总共的爬楼梯的方案数
例如：1-100的台阶，每个台阶随机权重，每次只能走一个或者两个台阶，找出从1-100最短路径
递归法：

private static int calculateCount(int ladder, int maxJump) {
    int jump = 0;
    if (ladder == 0) {
        return 1;//ladder=0，进入到最底层，记做一种走法
    }
    if (ladder >= maxJump) { // 剩下的楼梯大于最大可跳跃数
       for (int i = 1; i <= maxJump; i++) {
               jump += calculateCount(ladder - i, maxJump);
            }
             }
else {
       // 剩下的楼梯不足最大可跳跃数
      jump = calculateCount(ladder, ladder);
} return jump; }

二、非递归实现（动态规划）：(局限就是只能是1或2步)
当楼梯数为1、2、3、4、5时，对应的爬法有：1、2、3、5、8、13、21种。
可以发现，随着楼梯数n的增加，爬法总数呈现斐波那契数列规律增加，即f（n） = f（n-1） + f（n-2）
知道这个规律后，使用下面的循环即可实现：

public int count(int n){
    if(n==1 || n==2){
        return n;
    }
    int a = 1;
    int b = 2;
    int total;    
    for(int i=3;i<=n;i++){
        int temp = b;
        b = a + b;
        a = temp;
    }
    return b;
}