动态规划 - 70. 爬楼梯

Problem: 70. 爬楼梯

思路

定义一个哈希数组dp，缓存一下结果

解题过程

go(nowUpStair):

1. 由于1级台阶有1种方法，2级台阶有2种方法，所以可以写出递归出口：

xxxxxxxxxx
if (nowUpStair == 1 || nowUpStair == 2) {
    return nowUpStair;
}

2. 如果在dp中找到了上nowUpStair级的方案，那么直接返回它

3. 否则，就保存上nowUpStair级的方案

复杂度

• 时间复杂度: $O(N)$$O(N)$ 使用了大小为$N$$N$的缓存dp

• 空间复杂度: $O(N)$$O(N)$

Code

C++

xxxxxxxxxx
class Solution {
public:
    int climbStairs(int n) {
        return go(n);
    }
private:
    unordered_map<int, int> dp;
    int go(int nowUpStair) {
        if (nowUpStair == 1 || nowUpStair == 2) {
            return nowUpStair;
        }
        if (dp.count(nowUpStair)) {
            return dp[nowUpStair];
        }
        int ans = go(nowUpStair - 2) + go(nowUpStair - 1);
        dp[nowUpStair] = ans;
        return ans;
    }
};

Python

xxxxxxxxxx
dp = {}
def go(nowUpStair: int) -> int:
    if (nowUpStair == 1 or nowUpStair == 2):
        return nowUpStair
    if (nowUpStair in dp != 0):
        return dp[nowUpStair]
    ans = go(nowUpStair - 2) + go(nowUpStair - 1)
    dp[nowUpStair] = ans
    return ans
class Solution:
    def climbStairs(self, n: int) -> int:
        return go(n)

C#

public class Solution {
    Hashtable dp = new Hashtable();
    int go(int nowUpStair) {
        if (nowUpStair == 1 || nowUpStair == 2) {
            return nowUpStair;
        }
        if (dp.Contains(nowUpStair)) {
            return (int)dp[nowUpStair];
        }
        int ans = go(nowUpStair - 2) + go(nowUpStair - 1);
        dp.Add(nowUpStair, ans);
        return ans;
    }
    public int ClimbStairs(int n) {
        return go(n);
    }
}