题目

A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child
can run up the stairs.

大意

让你上n级的楼梯，每次可以走1，2，3级，3种选择，那么走到n级一共有几种组合

题解

通过 递归和 迭代(数学归纳)来解决
递归的表现力根强 但是算法的复杂度较高。
前者O(3^n) 后者 O(n)

package CC150;

public class _901_上楼梯 {
    static int count = 0;
    /**
     * 递归
     * n较小的时候会超时 效率低
     * 倒着写 顺这看
     * O(3^n)
     *
     * @param n
     * @return
     */
    public static int rec(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;

        return rec(n - 1) + rec(n - 2) + rec(n - 3);
    }

    /**
     * 迭代法 通过数学规律
     * 1 2 4 7 13 24
     * O(n)
     * @param n
     * @return
     */
    public static int inter(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 4;
        int x1=1;
        int x2=2;
        int x3=4;
        for (int i = 4; i <= n; i++) {
            int x_1=x1;
             x1=x2;
             x2=x3;
             x3=x_1+x1+x2;//递推公式 n=(n-1)+(n-2)-(n-3)
        }
        return x3;
    }

    public static void main(String[] args) {
        System.out.println(rec(10));
        System.out.println(inter(10));
    }
}

GitHub