解题思路

首先顶楼<=2时直接返回n就行了

我们可以这么思考，每个台阶都是由他的前一个台阶和前前一个台阶上来的，而这两个台阶也是同理。

那么我们只要从前往后遍历(下标从3开始)，每次将当前台阶的前两个台阶加起来，那么就是当前台阶的方法

推导公式：dp[i] = dp[i - 1] + dp[i - 2]

代码

Python

1
2
3
4
5
6
7
8
9
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2: return n
        dp = [0 for _ in range(n + 1)]
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        vector<int> dp(n + 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i < n + 1; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

GO

func climbStairs(n int) int {
    if n <= 2 {return n}
    dp := make([]int, n + 1, n + 1)
    dp[1] = 1
    dp[2] = 2
    for i := 3; i < n + 1; i++ {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}