题目

类型：动态规划

难度：简单

解题思路

方法一：动态规划

f(x)=f(x−1)+f(x−2)

意思是爬到第 x 级台阶的方案数是爬到第 x - 1级台阶的方案数和爬到第 x−2 级台阶的方案数的和。因为每次只能爬 1 级或 2 级，所以f(x) 只能从 f(x - 1) 和 f(x - 2)转移过来，而这里要统计方案总数就需要对这两项求和。

方法二：通项公式

根据 f(x)=f(x−1)+f(x−2) 可以推导公式

代码

方法一：

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

方法二：

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) Math.round(fibn / sqrt5);
    }
}