python動態規劃算法實例詳解

如果大家對這個生僻的術語不理解的話，那就先聽小編給大家說個現實生活中的實際案例吧，雖然現在手機是相當的便捷，還可以付款，但是最初的時候，我們經常會使用硬幣，其中，我們如果遇到手中有很多五毛或者1塊錢硬幣，要怎么湊出來5元錢呢？這么一個過程也可以稱之為動態規劃算法，下面就來看下詳細內容吧。

從斐波那契數列看動態規劃

斐波那契數列：Fn = Fn-1 + Fn-2 （ n = 1,2 fib(1) = fib(2) = 1）

練習：使用遞歸和非遞歸的方法來求解斐波那契數列的第 n 項

代碼如下：

# _*_coding:utf-8_*_def fibnacci(n): if n == 1 or n == 2: return 1 else: return fibnacci(n - 1) + fibnacci(n - 2) print(fibnacci(10)) # 55

如果看不懂上面模棱兩可的介紹，還有下面直觀的代碼：

f(1) = 1f(2) = 1f(3) = f(1) + f(2) = 1+ 1 = 2f(4) = f(3) + f(2) = 2 + 1 = 3...f(n) = f(n-1) + f(n-2)

實例擴展：

爬樓梯

假設你正在爬樓梯，需要n階才能到達樓頂每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？注意：給定 n 是一個正整數。如：示例1：輸入： 2輸出： 2解釋： 有兩種方法可以爬到樓頂。1. 1 階 + 1 階2. 2 階示例2：輸入： 3輸出： 3解釋： 有三種方法可以爬到樓頂。1. 1 階 + 1 階 + 1 階2. 1 階 + 2 階3. 2 階 + 1 階

解析：

如果給的兩個示例看的不是特別清楚，你可以當階梯為0，那么上樓梯方法0種這是必然，當階梯只有1那么上樓梯方法只有1種：當4個臺階：輸入：4輸出：41. 1階 + 1階 + 1階 + 1階2. 2階 + 2階3. 1階 + 2階 + 1階4. 2階 + 1階 + 1階5. 1階 + 1階 + 2階那么得到：階梯數 爬樓梯方法0 01 12 23 34 5...如果感覺看的不明顯可以推理一下5階，6階...可以得到當我們想爬n階樓梯，我們可以得到： p(n-1) + p(n-2) p為爬樓梯方法

class Solution: def climbStairs(self, n: int) -> int: num_list = [0,1,2] if n==1: return num_list[1] elif n==2: return num_list[2] else: for i in range(3,n+1):num_list.append(num_list[i-1]+num_list[i-2]) print(num_list) return num_list[n]obj = Solution()result = obj.climbStairs(10)print(result)

提交LeetCode只擊敗了12.72%的人。通過優化

class Solution: def climbStairs(self, n: int) -> int: a,b,c = 0,1,2 if n == 1: return b if n == 2: return c while n>0: c = a + b a,b = b,c n -= 1 return cobj = Solution()result = obj.climbStairs(8)

到此這篇關于python動態規劃算法實例詳解的文章就介紹到這了,更多相關python動態規劃算法是什么內容請搜索好吧啦網以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持好吧啦網！