public class Leedcode70{

    public static void main(String[] args) {
        Leedcode70 leedcode70 = new Leedcode70();
        int res = leedcode70.climbStairs(2);
        System.out.println(res);
        res = leedcode70.climbStairs(4);
        System.out.println(res);
        res = leedcode70.climbStairs(5);
        System.out.println(res);
        res = leedcode70.climbStairs(70);
        System.out.println(res);
    }
    // 简化的动态规划
    public int climbStairs(int n) {
        if (n == 1 || n ==  2) return n;
        int f1 = 1;
        int f2 = 2;
        int count = 3;
        while (count <= n){
            int t = f2;
            f2 = f1 + f2;
            f1 = t;
            count ++;
        }
        return f2;
    }
}

题解

1、暴力递归

存在大量的重复计算.

时间 $O(2^n)$
空间 $O(n)$

public class Solution {
    public int climbStairs(int n) {
        climb_Stairs(0, n);
    }
    public int climb_Stairs(int i, int n) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
    }
}

2、记忆化递归

时间 $O(n)$
空间 $O(n)$

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

3、动态规划

每个数字是一个状态: dp[n], 存在如下状态递推关系：

dp[n] = dp[n-1] + dp[n-2], n >= 2

复杂度分析：

时间 $O(n)$
空间 $O(n)$

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

4、利用斐波那契数的方法

时间 $O(n)$
空间 $O(1)$

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
}

5、Binets 方法

利用矩阵的相乘的方法求。
$F_n = Q^n[0,0]$
$$
Q^n =
\begin{bmatrix}
F_{n+1} & F_{n} \
F_{n} & F_{n-1}
\end{bmatrix}
$$

证明：
$$
Q^n = Q^{n-1} ·
\begin{bmatrix}
1 & 1 \
1 & 0
\end{bmatrix}

\begin{bmatrix}
F_{n} & F_{n-1} \
F_{n-1} & F_{n-2}
\end{bmatrix}
·
\begin{bmatrix}
1 & 1 \
1 & 0
\end{bmatrix}

\begin{bmatrix}
F_{n} + F_{n-1} & F_{n} \
F_{n-1} + F_{n-2} & F_{n-1}
\end{bmatrix}

\begin{bmatrix}
F_{n+1} & F_{n} \
F_{n} & F_{n-1}
\end{bmatrix}
$$

时间 $O(log(n))$
空间 $O(1)$

 public class Solution {
    public int climbStairs(int n) {
        int[][] q = {{1, 1}, {1, 0}};
        int[][] res = pow(q, n);
        return res[0][0];
    }
    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }
    public int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }
}

6、斐波那契公式求解

已经证明的斐波那契公式：
$$
f(n) = 1/\sqrt{5}·((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n)
$$

时间 $O(log(n))$ pow的耗时
空间 $O(1)$

public class Solution {
    public int climbStairs(int n) {
        double sqrt5=Math.sqrt(5);
        double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
        return (int)(fibn/sqrt5);
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com