亚洲热无码AV一区_中文字幕亚洲一区一区_欧美亚洲永久在线_在线观看亚洲精品自拍

藍鷗旗下品牌:鷗課學院
全國咨詢電話:13152008057
您的位置: 首頁 > 技術文章 > Python算法:如何解決樓梯臺階問題

Python算法:如何解決樓梯臺階問題

2021-09-14 藍鷗
5661人 瀏覽:

Python算法:如何解決樓梯臺階問題讓我們考慮以下問題。

有一個有N個臺階的樓梯,你一次可以爬1或2個臺階。

給定N,編寫一個函數(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ù)字爬樓梯,那會怎么樣?例如,如果X = {1,3,5},則表示一次爬升1,3或5階樓梯。

python-staircase-problem.jpg

解決方案

從一些測試案例開始總是好的做法。讓我們從小的案例開始,看看能否找到某種規(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]

你有沒有注意到什么?請看N = 3時,爬完3階樓梯的方法數(shù)量是3,基于N = 1和N = 2。存在什么關系?

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

這對N = 4是否成立呢?是的,這也是成立的。因為我們只能在達到第三個臺階然后再爬一步,或者在到了第二個臺階之后再爬兩步這兩種方式爬完4個臺階。所以f(4) = f(3) + f(2)。

所以關系如下: 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)

當然,這很慢(O(2^N))——我們要做很多重復的計算!通過迭代計算,我們可以更快:

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

現(xiàn)在,讓我們嘗試概括我們學到的東西,看看是否可以應用到從集合X中取步數(shù)這個要求下的爬樓梯。類似的推理告訴我們,如果X = {1,3,5},那么我們的算法應該是f(n) = f(n – 1) + f(n – 3) + f(n – 5)。如果n <0,那么我們應該返回0,因為我們不能爬負數(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)),因為也重復計算了。我們可以使用動態(tài)編程來加快速度。

每次的輸入cache[i]將包含我們可以用集合X到達臺階i的方法的數(shù)量。然后,我們將使用與之前相同的遞歸從零開始構建數(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)在時間復雜度為O(N * |X|),空間復雜度為O(N)。


  1. 廣告1
  2. 廣告2
  3. 廣告3
  4. 廣告4