Leetcode70 爬楼梯

题目描述

file

解法:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 1:
            return 0
        memory = {}
        memory[1] = 1
        memory[2] = 2
        for i in range(3, n+1):
            memory[i] = memory[i-1] + memory[i-2]
        return memory[n]
 

解析:

解题思路:
f(n) 代表跳 n 个台阶有多少种可能的路线
f(n-1)代表如果第一次跳的时候,跳的是 1 个台阶,剩下的 n-1 台阶有几种可能的路线
f(n-2)代表如果第一次跳的时候,跳的是 2 个台阶,剩下的 n-2 台阶有几种可能的路线
因为第一次跳的时候,可以跳 1 个台阶,也可以跳两个台阶,两种可能都有
所以总的可能性 f(n) = f(n-1) + f(n-2)

或者这么思考更直观些
file