7.2走楼梯

有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶,2阶,3阶,请实现一个方法,计算小孩有多少种上楼梯的方式.
为了防止溢出,请将结果模以mod 1000000007

给定一个正整数int n,请返回一个数,代表上楼的方式数.
保证n小于等于100000.

什么是递归,看起来是从上往下处理问题,这是现象,
实际上是从小往上处理问题,这是本质.
执行完最小最小的那个不可分割的问题,然后返回一个数值用于上一层使用,这就是递归的核心思想.

递归解法思路:
最小的不可分割问题有3个
第一个,当台阶n == 0时,此时有1种走法,就是不动.
第二个,当台阶n==1时,有1种走法,即走1步.
第三个,当台阶n==2时,有2种走法,即一步一步上去,或者一下子走两步.

有了这三个基本问题后,剩下的就是类似的子问题.
当n == 3时,如果先走1步,那么就剩下两阶,从这三个基本问题中的n==2可以得出结果,如果要走上第三阶,那么就有2种走法.
如果先走2步,那么就剩下一阶,从这三个基本问题中的n==1中可以得出结果,如果要走上第三阶,有1种走法.
如果先走3步,那么就剩下零阶,从这三个基本问题中的n==0中可以得出结果,即只有1种走法.
那么n == 3时,一共有1+1+2=4种走法,依次类推.
从子问题到大问题,就是递归的思想,每次return返回的都是下面一层的值,返回到上一层来使用

图片.png

    迭代的思想:
    何为之迭代,即在知道循环的次数之后,用循环来实现递归的解法.
第一步就是先初始化基本条件.
第二步,循环,使用基本条件来不断更新下一个循环的值

package _7节;

public class _7_2爬楼梯 {
    public static void main(String[] args) {
        System.out.println(climbFloor(5));
        System.out.println(climbFloor(5));
    }

    /*
        递归
     */
    public static int climbFloor(int n) {
        if (n < 0)
            return 0;
        if (n == 0 || n == 1)
            return 1;
        if (n == 2)
            return 2;
        return climbFloor(n - 1) + climbFloor(n - 2) + climbFloor(n - 3);
    }

    /*
        迭代,即循环,知道循环的次数
     */
    public static int climbFloorDiedai(int n) {
        if (n < 0)
            return 0;
        if (n == 0 || n == 1)
            return 1;
        if (n == 2)
            return 2;
        if (n == 3)
            return 4;
        int n1 = 1;
        int n2 = 2;
        int n3 = 4;

        for (int i = 4; i <= n; i++) {
            int _n1 = n1;
            n1 = n2;
            n2 = n3;
            n3 = ((n1 + n2) % 1000000007 + _n1) % 1000000007;
        }
        return n3;
    }
}