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

我想问一道 LeetCode 变形题:(70)爬楼梯(变形)

  •  
  •   hejw19970413 · 2020-06-12 10:59:05 +08:00 · 5786 次点击
    这是一个创建于 1386 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

    每次你可以爬 1 或 2 或 3 个台阶,且每次上的台阶不相同。你有多少种不同的方法可以爬到楼顶呢?

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

    哥哥们 这个变形 怎么解答 ? 怎么个思路 ?

    56 条回复    2020-06-24 10:11:17 +08:00
    hejw19970413
        1
    hejw19970413  
    OP
       2020-06-12 11:02:27 +08:00
    有没有大佬可以试着解决一下 ,弟弟想了一宿没思路
    hello2060
        2
    hello2060  
       2020-06-12 11:05:40 +08:00
    很难吗?开一个数组 int ways[n + 1], 答案是 ways[n] 初始化 ways[0] = 1, ways[1] = 1, ways[2] = 2, ways[3] = xx, ways[n] = ways[n - 1] + ways[n - 2] + ways[n - 3] ? 什么叫每次上的台阶不同
    Vegetable
        3
    Vegetable  
       2020-06-12 11:05:41 +08:00
    什么叫每次上的台阶不同?还能有相同的?
    winterfell30
        4
    winterfell30  
       2020-06-12 11:08:53 +08:00   ❤️ 1
    斐波那契数列
    Vegetable
        5
    Vegetable  
       2020-06-12 11:10:27 +08:00
    有点读懂了,试说每次上的台阶数不能与上一步相同?这个也算变种吗?可以说这是变了个数吧
    VoidChen
        6
    VoidChen  
       2020-06-12 11:11:43 +08:00
    我想问下有没有好的刷 leecode 的总结。。之前在 github 看到一个按算法类型来分类的,我不知道保存到哪没了。。
    cheese
        7
    cheese  
       2020-06-12 11:15:09 +08:00
    @hello2060 #2
    @Vegetable #3
    应该的意思是,爬过 1 之后,下一次只能 2,3 。每次的选择台阶数,不能和上一次的数字相同
    leavan
        8
    leavan  
       2020-06-12 11:16:04 +08:00
    哦我懂了,就是其他方法走过一次的楼梯不能再走了呗。那不是很简单吗?从楼顶往回看,最多只有三个台阶可以一步到楼顶,那么我们只需要证明这三种方法都可行就行了,每次都往前各推三步(如果有一个不是三步的,那么势必会造成重复),发现推到边界处仍然不会重复,所以有三种方法。答案就是 3,当然如果你 n 只有 1 或 2 的话那么方法也相应减少。
    coderraven
        9
    coderraven  
       2020-06-12 11:16:10 +08:00
    怎么有点二叉树的感觉
    用过 1,那么左右子树就只能是 2 和 3 。
    用过 2,那么左右子树就只能是 1 和 3.
    用过 3….

    最后再走一波数值和是 n 的遍历?
    leavan
        10
    leavan  
       2020-06-12 11:17:35 +08:00
    @leavan 无视我这条,看了大家的回复发现我理解题意了。
    zhjy23212
        11
    zhjy23212  
       2020-06-12 11:17:40 +08:00
    dp 里面每个状态存之前到这个点的步数,下次遍历跳过这几个。

    基本上是 frog jump 的变体
    hejw19970413
        12
    hejw19970413  
    OP
       2020-06-12 11:17:57 +08:00
    @Vegetable 比如 上 2 阶 只可以一次性上 2 级 不能是 1 级 1 级
    EggtartZ
        13
    EggtartZ  
       2020-06-12 11:18:59 +08:00
    `dp[n, 1] = dp[n - 3, 2] + dp[n - 4, 3]` 这样的意思?
    leavan
        14
    leavan  
       2020-06-12 11:21:19 +08:00
    如果是跟上一步的台阶不同的话,那就动态规划。
    ```
    ways[i][0] = ways[i - 1][1] + ways[i - 1][2]
    ways[i][1] = ways[i - 2][0] + ways[i - 2][2]
    ways[i][2] = ways[i - 3][0] + ways[i - 3][1]
    ```
    hello2060
        15
    hello2060  
       2020-06-12 11:21:36 +08:00
    那就不要 int[n + 1] 搞一个数据结构,每一个位置存着 1.到这里的总方法数 2. 前一步是 n-1 的方法书 3.前一步是 n-2 的方法数 4.前一步是 n - 3 的方法数

    那你到 n 的方法数 就是 走 2,3 到 n-1 的方法数 + 走 1,3 到 n -2 的方法数 + 走 1,2 到 n-3 的方法数
    hejw19970413
        16
    hejw19970413  
    OP
       2020-06-12 11:22:37 +08:00
    @hello2060 大佬 你这个第三个不对啊。1+1+2 = 4 第三级 那有 4 种啊 3 ,12 ,21
    hello2060
        17
    hello2060  
       2020-06-12 11:23:58 +08:00
    @hejw19970413 第三个我不是没算嘛 xx 反正就那个意思,哈哈
    Vegetable
        18
    Vegetable  
       2020-06-12 11:37:50 +08:00
    大概想了一下
    可以重复的时候,dp(n) = dp(n-1)+dp(n-2)+dp(n-3)
    不能重复的话,计算点 n 时,从 n-2 到 n-1 这一点的数据都是要去掉的,n-4 到 n-2 要去掉,n-6 到 n-3 要去掉。
    所以 dp(n) = (dp(n-1) - dp(n-2)) + (dp(n-2)-dp(n-4))+(dp(n-3)-dp(n-6))
    是这样吗
    hejw19970413
        19
    hejw19970413  
    OP
       2020-06-12 11:41:55 +08:00
    @Vegetable 我去跑一下
    xw900812
        20
    xw900812  
       2020-06-12 11:47:53 +08:00
    dynamic programming... YouTube 搜 huahua leetcode 讲这道爬楼梯的问题,很经典的 DP 题目
    buhi
        21
    buhi  
       2020-06-12 11:50:28 +08:00
    第一个题就是斐波那契数列, 答 dp 的都输了
    const stair_ways = n => {
    return Math.round((1 / sqrt_5) * Math.pow((1 + sqrt_5) / 2, n + 1) - (1 / sqrt_5) * Math.pow((1 - sqrt_5) / 2, n + 1))
    }
    MoYi123
        22
    MoYi123  
       2020-06-12 11:51:45 +08:00
    三个数字的斐波那契数列
    EggtartZ
        23
    EggtartZ  
       2020-06-12 11:53:45 +08:00
    ```
    def solve(n, m):
    dp = [[0] * m for i in range(n)]
    for i in range(m):
    dp[i][i] = 1
    for j in range(i):
    dp[i][j] = sum(dp[i - j - 1]) - dp[i - j - 1][j]

    for i in range(m, n):
    for j in range(m):
    dp[i][j] = sum(dp[i - j - 1]) - dp[i - j - 1][j]

    return sum(dp[n - 1])
    ```
    大概是这样吧
    mymike
        24
    mymike  
       2020-06-12 11:55:21 +08:00 via iPhone
    这个和最近的刷房子类似 需要加一个维度
    larisboy
        25
    larisboy  
       2020-06-12 11:55:24 +08:00
    数组+斐波那契数列
    hello2060
        26
    hello2060  
       2020-06-12 11:58:29 +08:00
    @buhi 斐波那契就是 DP 啊,一个问题可以分解成类似的子问题,而且子问题的解有重复的地方。
    buhi
        27
    buhi  
       2020-06-12 12:04:10 +08:00
    算斐波那契是 O(1), dp 不是 O(1)
    hejw19970413
        28
    hejw19970413  
    OP
       2020-06-12 12:15:30 +08:00
    @buhi 大佬。按照您的公式算出来 答案不对
    hejw19970413
        29
    hejw19970413  
    OP
       2020-06-12 12:18:18 +08:00
    @Vegetable 我需要手动算到 6 还是 7 啊
    lxy42
        30
    lxy42  
       2020-06-12 12:20:03 +08:00
    ```python
    def walk_dp(n):
    dp = collections.deque([[1, 0, 0], [0, 1, 0], [1, 1, 1]])
    for _ in range(3, n):
    d = [dp[-1][1] + dp[-1][2],
    dp[-2][0] + dp[-2][2],
    dp[-3][0] + dp[-3][1],
    ]
    dp.append(d)
    dp.popleft()
    return sum(dp[-1])
    ```
    hejw19970413
        31
    hejw19970413  
    OP
       2020-06-12 12:21:27 +08:00
    @EggtartZ 您这个 m 是啥?
    hejw19970413
        32
    hejw19970413  
    OP
       2020-06-12 12:23:41 +08:00
    @lxy42 大佬。您这个从 4 开始都是 3
    levelworm
        33
    levelworm  
       2020-06-12 12:25:59 +08:00 via Android
    这个感觉和分硬币有点像,总共 X 美元,有 5 分,一毛,25 分,50 分以及一美元,求问总共有几种分法。SICP 上第一章有答案。
    levelworm
        34
    levelworm  
       2020-06-12 12:28:47 +08:00 via Android
    我直接抄书,我认为这个分硬币和上楼梯是一个事情。

    they are calculating the number (N) of ways of change a quatity (A) using K kinds of coins by adding:

    1. the number of ways (X) of changing A without coins of the first type.

    2.The number of ways (Y) of changing (A - D), where D is the denomination of the fisrt coin, using ALL K types of coins.
    hejw19970413
        35
    hejw19970413  
    OP
       2020-06-12 12:30:17 +08:00
    @levelworm 这个相似的题,我都是看到了。到现在我就不明白是在 怎么才能做到不重复。
    EggtartZ
        36
    EggtartZ  
       2020-06-12 12:40:56 +08:00
    @hejw19970413 m 是每次最多走的台阶数,3 就是每次能走 1,2 或 3 格
    hejw19970413
        37
    hejw19970413  
    OP
       2020-06-12 12:46:15 +08:00
    @EggtartZ 你这个好像是对的耶 !厉害了 我的哥
    freemon
        38
    freemon  
       2020-06-12 12:49:23 +08:00   ❤️ 1
    原题比较简单哈,变异之后用 dp 就好
    定义 s[i][k] 为到达地 i 层阶梯且最后一步走 k 步的 走法数量

    s[i][1] = s[i-1][2]+s[i-2][3]
    s[i][2] = s[i-2][1]+s[i-2][3]
    s[i][3] = s[i-3][1]+s[i-3][2]

    确定一下初始值,然后计算 result = s[n][1]+s[n][2]+s[n][3] 即可 ?
    buhi
        39
    buhi  
       2020-06-12 12:50:27 +08:00
    f(n) = f(n-1) + f(n-2) + f(n-3), 求 f(n), 这个存在 O(1)的解法.
    https://www.fq.math.ca/Scanned/20-2/spickerman.pdf
    (就是浮点数计算的话, 台阶数高了之后就误差很大了)
    hejw19970413
        40
    hejw19970413  
    OP
       2020-06-12 12:56:06 +08:00
    @buhi 哥你这个我有点晕
    hejw19970413
        41
    hejw19970413  
    OP
       2020-06-12 12:56:22 +08:00
    @freemon 好 我理解下
    Vegetable
        42
    Vegetable  
       2020-06-12 13:02:41 +08:00
    @hejw19970413 #29 我那个思路减错啦
    lylsh1993
        43
    lylsh1993  
       2020-06-12 13:33:02 +08:00 via iPhone
    #30 楼 正解
    doudou1523102
        44
    doudou1523102  
       2020-06-12 18:16:22 +08:00
    关键字 “多少种” 这种要用动态规划区想了
    pangleon
        45
    pangleon  
       2020-06-12 19:39:12 +08:00
    这道题好做就是怎么能不报错,用迭代加备忘录一样会 stackoverflow
    BBCCBB
        46
    BBCCBB  
       2020-06-12 19:45:30 +08:00
    兄弟, 斐波数列

    你百度一下一堆. 比在 v 站问高效啊.
    BBCCBB
        47
    BBCCBB  
       2020-06-12 19:47:29 +08:00
    而且这种 leetcode 的题一搜也是一堆思路解析. 多刷刷,多理解你就有感觉了
    octobered
        48
    octobered  
       2020-06-12 21:04:45 +08:00
    面经题熟脸了.... 今年最少被问了三次这道题了 斐波那契完事
    nznd
        49
    nznd  
       2020-06-13 01:35:09 +08:00
    ```python
    if n==1:
    return 1
    first,second=1,2
    for _ in range(3,n+1):
    first,second=second,first+second
    return second
    ```
    一个 空间 o(1) 时间 o(n)的解法(简单易懂
    ericgui
        50
    ericgui  
       2020-06-22 01:28:30 +08:00
    https://www.bilibili.com/video/BV1G54y1X72H

    这是我讲的爬楼梯 70 题

    其实变形就是 dp[k] = dp[k-1] + dp[k-2] + dp[k-3]

    思路是一样的思路
    hejw19970413
        51
    hejw19970413  
    OP
       2020-06-23 19:57:08 +08:00
    @ericgui 您成功的耽误了我 10 分钟。
    ericgui
        52
    ericgui  
       2020-06-24 00:37:58 +08:00
    @hejw19970413 讲的不好?耽误您时间了,不好意思
    hejw19970413
        53
    hejw19970413  
    OP
       2020-06-24 09:54:35 +08:00
    @ericgui 不是您讲的不好,只不过你说的和我题,完全不是一个概念,是都是用斐波那契数列 , 你只要说我这个道变形题的痛点,和怎么考虑就好了。不同的斐波那契数列,可以玩成不同的解决办法。 您就比如说 变形题中的 上的台阶不相同 怎么考虑 , 1 或 2 或 3 个台阶 怎么考虑 ? 如果我要是 说 用斐波那契数列 就知道了怎么解决,就不会来问了 。
    hejw19970413
        54
    hejw19970413  
    OP
       2020-06-24 09:56:52 +08:00
    @ericgui 也就可以打一个比方,我想吃饭,问西红柿炒鸡蛋怎么做,你说去买西红柿和鸡蛋 然后 加热 就 OK 了,您所说的是对的,也非常的好,但是不能解决我的问题。 大佬
    hejw19970413
        55
    hejw19970413  
    OP
       2020-06-24 09:59:33 +08:00
    这里的每一条回复我都去做了验证。。 包括所说的公式什么的,第 23 层我认为是正确的,第 30 层的得出来的结果有些偏差,普通的公式得出来的结果,只是适用为 前两个数之和。
    ericgui
        56
    ericgui  
       2020-06-24 10:11:17 +08:00
    @hejw19970413 不好意思哈
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3176 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 10:53 · PVG 18:53 · LAX 03:53 · JFK 06:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.