题解 | #跳台阶#

from typing import Dict

class Solution:
    memo: Dict[int, int] = dict()
    def jumpFloor(self , number: int) -> int:
        if number < 0:
            return 0
        if number == 0:
            return 1
        if number in self.memo:
            return self.memo.get(number)
        ans = self.jumpFloor(number - 1) + self.jumpFloor(number - 2)
        self.memo[number] = ans
        return ans

时间复杂度：O(n)

空间复杂度：O(n) + 递归栈的空间

解法：找到递推关系，发现基本情况，使用记忆化搜索