跳台阶

跳台阶_牛客题霸_牛客网

问题简述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

思路

• dp(i) := dp(i-1) + dp(i-2)

Python

class Solution:
    def jumpFloor(self , n: int) -> int:
        
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(i):
            if i == 1: return 1
            if i == 2: return 2
            
            return dp(i - 1) + dp(i - 2)
        
        return dp(n)