4

[每天一道LeetCode] 70. 爬楼梯

 3 years ago
source link: https://doumao.cc/index.php/%E7%BC%96%E7%A8%8B/%E6%AF%8F%E5%A4%A9%E4%B8%80%E9%81%93LeetCode-70-%E7%88%AC%E6%A5%BC%E6%A2%AF.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

[每天一道LeetCode] 70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

不难发现，爬上n级，可以由n-1再爬1级，或者由n-2再爬2级。
所以爬上n级阶梯的方法数 = 爬上n-1级阶梯的方法数 + 爬上n-2级阶梯的方法数

我们可以使用递归的方法来解答，但我们可以使用动态规划来优化递归问题。我们已经将原问题分解成子问题，我们可以从解子问题来得出原问题的解。

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n

        first, second = 1, 2
        for i in range(3, n+1):
            third = first + second
            first, second = second, third
        return third

时间复杂度O(n)，空间复杂度O(1)。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK