Python算法：如何解決樓梯臺(tái)階問題

Python算法：如何解決樓梯臺(tái)階問題讓我們考慮以下問題。

有一個(gè)有N個(gè)臺(tái)階的樓梯，你一次可以爬1或2個(gè)臺(tái)階。

給定N，編寫一個(gè)函數(shù)，返回爬完樓梯的方式數(shù)量。步驟的順序很重要。

例如，如果N是4，那么有5種方式：

• 1,1,1,1

• 2,1,1

• 1,2,1

• 1,1,2

• 2,2

如果規(guī)定的不是一次只能爬1或2步，而是可以使用正整數(shù)X集合內(nèi)的任意數(shù)字爬樓梯，那會(huì)怎么樣？例如，如果X = {1,3,5}，則表示一次爬升1，3或5階樓梯。

解決方案

從一些測試案例開始總是好的做法。讓我們從小的案例開始，看看能否找到某種規(guī)律。

• N = 1，1種爬樓方式：[1]

• N = 2，2種爬樓方式：[1,1]，[2]

• N = 3，3種爬樓方式：[1,2]，[1,1,1]，[2,1]

• N = 4，5種爬樓方式：[1,1,2]，[2,2]，[1,2,1]，[1,1,1,1]，[2,1,1]

你有沒有注意到什么？請(qǐng)看N = 3時(shí)，爬完3階樓梯的方法數(shù)量是3，基于N = 1和N = 2。存在什么關(guān)系？

爬完N = 3的兩種方法是首先達(dá)到N = 1，然后再往上爬2步，或達(dá)到N = 2再向上爬1步。所以 f(3) = f(2) + f(1)。

這對(duì)N = 4是否成立呢？是的，這也是成立的。因?yàn)槲覀冎荒茉谶_(dá)到第三個(gè)臺(tái)階然后再爬一步，或者在到了第二個(gè)臺(tái)階之后再爬兩步這兩種方式爬完4個(gè)臺(tái)階。所以f(4) = f(3) + f(2)。

所以關(guān)系如下： f(n) = f(n – 1) + f(n – 2)，且f(1) = 1和f(2) = 2。這就是斐波那契數(shù)列。

def fibonacci(n):
    if n <= 1:        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

當(dāng)然，這很慢（O(2^N)）——我們要做很多重復(fù)的計(jì)算！通過迭代計(jì)算，我們可以更快：

def fibonacci(n):
    a, b = 1, 2
    for _ in range(n - 1):
        a, b = b, a + b    return a

現(xiàn)在，讓我們嘗試概括我們學(xué)到的東西，看看是否可以應(yīng)用到從集合X中取步數(shù)這個(gè)要求下的爬樓梯。類似的推理告訴我們，如果X = {1,3,5}，那么我們的算法應(yīng)該是f(n) = f(n – 1) + f(n – 3) + f(n – 5)。如果n <0，那么我們應(yīng)該返回0，因?yàn)槲覀儾荒芘镭?fù)數(shù)。

def staircase(n, X):
    if n < 0:        return 0
    elif n == 0:        return 1
    elif n in X:        return 1 + sum(staircase(n - x, X) for x in X if x < n)    
    else:        return sum(staircase(n - x, X) for x in X if x < n)

這也很慢（O(|X|^N)），因?yàn)橐仓貜?fù)計(jì)算了。我們可以使用動(dòng)態(tài)編程來加快速度。

每次的輸入cache[i]將包含我們可以用集合X到達(dá)臺(tái)階i的方法的數(shù)量。然后，我們將使用與之前相同的遞歸從零開始構(gòu)建數(shù)組：

def staircase(n, X):
    cache = [0 for _ in range(n + 1)]
    cache[0] = 1
    for i in range(n + 1):
        cache[i] += sum(cache[i - x] for x in X if i - x > 0)
        cache[i] += 1 if i in X else 0
    return cache[-1]

現(xiàn)在時(shí)間復(fù)雜度為O(N * |X|)，空間復(fù)雜度為O(N)。