流水沉微

楼梯有多少种走法

这是在 telegram 网鱼网咖群里聊天时,Haruhi贴的一个题,题目如下:

wangyuwangka

思路很简单

可以从14、13、12级跨到第15级 f(15)=f(14)+f(13)+f(12)

递推公式出来鸟~

当然要得到一个答案是非常简单的

def ladder(N, m = 3):
    h = {}
    h[1] = 1
    h[2] = 2
    h[3] = 4
    for i in range(4, N+1):
        h[i] = h[i-1]+h[i-2]+h[i-3]
    print(h[N])

ladder(15)

狗叔:时间复杂度和空间复杂度?

我回答:

hash把每级阶梯的走法存下来,N级阶梯的话空间复杂度O(N),时间复杂度也是O(N),先用迭代从1开始迭代到N,然后最后加起来就行。递归的复杂度我就不知道该怎么分析了

狗叔:Hash的空间复杂度是多少?

回答:O(N)

santo: O(4) 就行了

有道理,因为只需要存 4 个值用来迭代就行了

santo还提了一个更加快捷得到答案的方法:

前四个列出来

奇偶偶奇, mod 4 = 0的是(1+0+0)%2; mod 4 = 1的是(1+1+0)%2, … 然后这题里只有一个偶数… 这种选择题, 应该是要人秒答? 所以随便蒙一下…

此外,Haruhi还发散了一下,如果总共 total 级阶梯,一次最多跨越 step 级,那有多少种方法?

于是我又给写了一下

def ladder(total, step):
    assert total > 0
    assert step > 0
    h = {}
    # 走完脚力范围内一次性可以走完的阶梯,获得迭代的基础
    for i in range(1, step + 1, 1):
        h[i] = sum([h[x] for x in range(1, i)])+1

    # 对不能一次走完的阶梯进行迭代
    for i in range(step + 1, total + 1, 1):
        # temp 是新的阶梯可能走的次数
        temp = sum([h[x] for x in range(1, step + 1)])
        # 挤占掉最小的一次阶梯 e.g. 
        # 1 2 4 ->
        # 2 4 7 ->
        # 4 7 13
        for j in range(1, step):
            h[j] = h[j+1]
        h[step] = temp
    
    # 兼容 total < step 的情况
    print(h[step] if total > step else h[total])

ladder(5, 3)