V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Acceml
V2EX  ›  程序员

[Leetcode] 70. 爬楼梯

  •  
  •   Acceml ·
    Acceml · 2018-09-25 00:01:24 +08:00 · 2683 次点击
    这是一个创建于 2243 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

    假设你正在爬楼梯。需要 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]
    

    热门文章

    12 条回复    2018-09-25 11:13:22 +08:00
    20015jjw
        1
    20015jjw  
       2018-09-25 00:43:35 +08:00 via Android
    这题解法也不够好 空间上可以 O(1)的
    rabbbit
        2
    rabbbit  
       2018-09-25 00:51:33 +08:00
    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
        3
    wwwaaa  
       2018-09-25 01:18:07 +08:00 via Android
    能问下什么是 DP 嘛
    dangyuluo
        4
    dangyuluo  
       2018-09-25 01:40:04 +08:00
    @wwwaaa dynamic programming
    动态规划
    aenon
        5
    aenon  
       2018-09-25 01:48:31 +08:00
    @rabbbit 用通项公式有什么弊端吗? 我看很少能见到这样的做法.
    XiaoxiaoPu
        6
    XiaoxiaoPu  
       2018-09-25 01:57:41 +08:00
    @aenon 乘方的计算并不是 O(1),浮点运算的误差累积导致结果有可能有偏差,浮点运算相比整数加法要慢得多
    afpro
        7
    afpro  
       2018-09-25 01:59:15 +08:00
    @aenon 知道通项公式的人不多而已。。
    Mirage09
        8
    Mirage09  
       2018-09-25 02:26:44 +08:00 via iPhone
    本来想说这种东西放到题目下面的 discussion 就可以了,往上一划发现有个二维码,好吧¯\_(ツ)_/¯
    layorlayor
        9
    layorlayor  
       2018-09-25 10:12:36 +08:00
    那进阶一下,n<=1e18, 结果对 1e9+7 取模
    earendil1412
        10
    earendil1412  
       2018-09-25 10:19:51 +08:00 via Android
    @XiaoxiaoPu 可以用矩阵来算[[1,1],[1,0]]的 n 次方
    mbtfdwlx
        11
    mbtfdwlx  
       2018-09-25 10:31:05 +08:00
    这不是就是斐波那契数列么 = =
    mbtfdwlx
        12
    mbtfdwlx  
       2018-09-25 11:13:22 +08:00
    递归的方法不好,因为存在大量重复计算。比如在计算 dp[5] = dp[4]+dp[3], 其中计算 dp[4] = dp[3]+dp[2]。发现其实 dp[3]计算了两次,数值越大,重复计算次数越多。两种解决方案,一是递归的时候记录 如果有过 dp[i], 直接返回。否则计算 dp[i]。二是用递推,从 1 推到 n,而不是从 n 递归到 1
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1855 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 16:38 · PVG 00:38 · LAX 08:38 · JFK 11:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.