有個小孩正在上樓梯,樓梯有n階臺階,小孩一次可以上1階,2階,3階,請實現(xiàn)一個方法,計算小孩有多少種上樓梯的方式.
為了防止溢出,請將結(jié)果模以mod 1000000007

給定一個正整數(shù)int n,請返回一個數(shù),代表上樓的方式數(shù).
保證n小于等于100000.

什么是遞歸,看起來是從上往下處理問題,這是現(xiàn)象,
實際上是從小往上處理問題,這是本質(zhì).
執(zhí)行完最小最小的那個不可分割的問題,然后返回一個數(shù)值用于上一層使用,這就是遞歸的核心思想.

遞歸解法思路:
最小的不可分割問題有3個
第一個,當臺階n == 0時,此時有1種走法,就是不動.
第二個,當臺階n==1時,有1種走法,即走1步.
第三個,當臺階n==2時,有2種走法,即一步一步上去,或者一下子走兩步.

有了這三個基本問題后,剩下的就是類似的子問題.
當n == 3時,如果先走1步,那么就剩下兩階,從這三個基本問題中的n==2可以得出結(jié)果,如果要走上第三階,那么就有2種走法.
如果先走2步,那么就剩下一階,從這三個基本問題中的n==1中可以得出結(jié)果,如果要走上第三階,有1種走法.
如果先走3步,那么就剩下零階,從這三個基本問題中的n==0中可以得出結(jié)果,即只有1種走法.
那么n == 3時,一共有1+1+2=4種走法,依次類推.
從子問題到大問題,就是遞歸的思想,每次return返回的都是下面一層的值,返回到上一層來使用

圖片.png

    迭代的思想:
    何為之迭代,即在知道循環(huán)的次數(shù)之后,用循環(huán)來實現(xiàn)遞歸的解法.
第一步就是先初始化基本條件.
第二步,循環(huán),使用基本條件來不斷更新下一個循環(huán)的值

package _7節(jié);

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);
    }

    /*
        迭代,即循環(huán),知道循環(huán)的次數(shù)
     */
    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;
    }
}