[Leetcode] 70. 爬楼梯

[Acceml]

题目

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

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

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

示例 1：

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

示例 2：

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

题解

这个题目只要模拟一下基本就能想到是 DP，状态方程写出来就是斐波那契数列。 dp[i] = dp[i-1] + dp[i-2] i-1 的时候跳一步可以到达 i i-2 的时候跳一步是 i-1，这个变成 dp[i-1]的子问题了,直接跳两步可以到达 i

java

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

python

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [1 for i in range(n + 1)]
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

热门文章

• [ Spring ] IOC 是啥有什么好处
• [ Leetcode ] 67. 二进制求和
• [ Leetcode ] 66. 加一

[20015jjw]

这题解法也不够好 空间上可以 O(1)的

[rabbbit]

var climbStairs = function (n) {
let sqrt5 = Math.sqrt(5);
let result = (Math.pow(((1 + sqrt5) / 2), n + 1) - Math.pow(((1 - sqrt5) / 2), n + 1)) / sqrt5;
return Number(result.toFixed());
};
O(1)

[wwwaaa]

能问下什么是 DP 嘛

[dangyuluo]

@wwwaaa dynamic programming
动态规划

[aenon]

@rabbbit 用通项公式有什么弊端吗? 我看很少能见到这样的做法.

[XiaoxiaoPu]

@aenon 乘方的计算并不是 O(1)，浮点运算的误差累积导致结果有可能有偏差，浮点运算相比整数加法要慢得多

[afpro]

@aenon 知道通项公式的人不多而已。。

[Mirage09]

本来想说这种东西放到题目下面的 discussion 就可以了，往上一划发现有个二维码，好吧¯\_(ツ)_/¯

[layorlayor]

那进阶一下，n<=1e18， 结果对 1e9+7 取模

[earendil1412]

@XiaoxiaoPu 可以用矩阵来算[[1,1],[1,0]]的 n 次方

[mbtfdwlx]

这不是就是斐波那契数列么 = =

[mbtfdwlx]

递归的方法不好，因为存在大量重复计算。比如在计算 dp[5] = dp[4]+dp[3], 其中计算 dp[4] = dp[3]+dp[2]。发现其实 dp[3]计算了两次，数值越大，重复计算次数越多。两种解决方案，一是递归的时候记录 如果有过 dp[i], 直接返回。否则计算 dp[i]。二是用递推，从 1 推到 n，而不是从 n 递归到 1