70.Climbing Stairs

25 年 8 月 4 日 星期一
110 字
1 分钟

70. Climbing Stairs

Recursion 递归 top down

python
class Solution:
    def climbStairs(self, n: int) -> int:
        @cache
        def dfs(i):
            if i == 1:
                return 1
            if i == 2:
                return 2
            return dfs(i-1) + dfs(i-2)
        return dfs(n)

递推 recurrence

python
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        f0 = 1
        f1 = 2
        for i in range(2, n):
            new_f = f0 + f1
            f0 = f1
            f1 = new_f
        return new_f
        # @cache
        # def dfs(i):
        #     if i == 1:
        #         return 1
        #     if i == 2:
        #         return 2
        #     return dfs(i-1) + dfs(i-2)
        # return dfs(n)

文章标题：70.Climbing Stairs

文章作者：Sirui Chen

文章链接：https://blog.siruichen.me/posts/70climbing_stairs[复制]

最后修改时间：

商业转载请联系站长获得授权，非商业转载请注明本文出处及文章链接，您可以自由地在任何媒体以任何形式复制和分发作品，也可以修改和创作，但是分发衍生作品时必须采用相同的许可协议。
本文采用CC BY-NC-SA 4.0进行许可。