假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數。

示例 1：

輸入： 2

輸出： 2

解釋： 有兩種方法可以爬到樓頂。

1 階 + 1 階

2 階

示例 2：

輸入： 3

輸出： 3

解釋： 有三種方法可以爬到樓頂。

1 階 + 1 階 + 1 階

1 階 + 2 階

2 階 + 1 階

原文章主要借由 2 個問題 來講述什么是動態規劃，由淺到深，本篇主要圍繞第1個問題，使用python 實現(文中使用java實現)。

第2個問題放在下一篇實現。

# 針對試題一 的解法

# 最優解 斐波拉契數列

class Solution(object):

def climbStairs(self, n):

"""

:type n: int

:rtype: int

時間復雜度: O(2^n) ; 這是一顆二叉樹,樹的高度 n-1 ,節點有 2^(n-1)

空間復雜度: O(2^n) ; 因為每個計算結果都要存儲,而且涉及重復計算

"""

assert isinstance(n,int),"n 不是整型,請確認后重新輸入"

assert (n > 0), "n 必須大于0,請確認后重新輸入"

if n <= 1:

return 1

elif n == 2:

return 2

return self.climbStairs(n-1)+self.climbStairs(n-2)

def climbStairs2(self, n, record=dict()):

"""

:type n: int

:rtype: int

備忘錄算法,通過一個緩存,來減少重復計算

時間復雜度: O(n) ; f1~fn 除去 1,2 確定,其他都有走一遍,即 n-2

空間復雜度: O(n) ; 同理

"""

assert isinstance(n,int),"n 不是整型,請確認后重新輸入"

assert (n > 0), "n 必須大于0,請確認后重新輸入"

if n <= 1:

return 1

if n == 2:

return 2

if record.keys().__contains__(n):

return record.get(n)

else:

res = self.climbStairs2(n-1,record)+self.climbStairs2(n-2,record)

record[n]= res

return res

def climbStairs3(self, n):

"""

:type n: int

:rtype: int

減少空間復雜度,自底向上

時間復雜度: O(n) ; f1~fn 除去 1,2 確定,其他都有走一遍,即 n-2

空間復雜度: O(1) ; 因為每個計算結果都要存儲兩個變量

"""

assert isinstance(n,int),"n 不是整型,請確認后重新輸入"

assert (n > 0), "n 必須大于0,請確認后重新輸入"

if n == 1:

return 1

elif n == 2:

return 2

a,b,temp = (1,2,0)

for i in range(3,n+1):

temp = a+b

a = b

b = temp

return temp

if __name__ == ‘__main__‘:

s = Solution()

# res = s.climbStairs(4)

# res = s.climbStairs2(4)

res = s.climbStairs3(4)

print(res)

思路: climbStairs函數 是原始解法,但時間及空間復雜度均很大 O(2^n), 考慮到有重復計算,

所以加個緩存備忘錄 字典record, 沒有的加進去,后續再遇到就直接從record中取值,沒必要再遞歸到最底層得到結果。即 climbStairs2 函數

再進一步考慮優化 空間復雜度，自底向上，每次只保留最近的兩個結果，即 climbStairs3 函數

原文：https://www.cnblogs.com/jason-Gan/p/13303601.html

總結

以上是生活随笔為你收集整理的python动态规划图解_动态规划案例之python实现（一）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。