如果大家對這個(gè)生僻的術(shù)語不理解的話，那就先聽小編給大家說個(gè)現(xiàn)實(shí)生活中的實(shí)際案例吧，雖然現(xiàn)在手機(jī)是相當(dāng)?shù)谋憬荩€可以付款，但是最初的時(shí)候，我們經(jīng)常會使用硬幣，其中，我們?nèi)绻龅绞种杏泻芏辔迕蛘?塊錢硬幣，要怎么湊出來5元錢呢？這么一個(gè)過程也可以稱之為動態(tài)規(guī)劃算法，下面就來看下詳細(xì)內(nèi)容吧。

從斐波那契數(shù)列看動態(tài)規(guī)劃

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

練習(xí)：使用遞歸和非遞歸的方法來求解斐波那契數(shù)列的第 n 項(xiàng)

代碼如下：

# _*_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)

實(shí)例擴(kuò)展：

爬樓梯

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

解析：

如果給的兩個(gè)示例看的不是特別清楚，你可以當(dāng)階梯為0，那么上樓梯方法0種這是必然，當(dāng)階梯只有1那么上樓梯方法只有1種：當(dāng)4個(gè)臺階：輸入：4輸出：41. 1階 + 1階 + 1階 + 1階2. 2階 + 2階3. 1階 + 2階 + 1階4. 2階 + 1階 + 1階5. 1階 + 1階 + 2階那么得到：階梯數(shù) 爬樓梯方法0 01 12 23 34 5...如果感覺看的不明顯可以推理一下5階，6階...可以得到當(dāng)我們想爬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%的人。通過優(yōu)化

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)

到此這篇關(guān)于python動態(tài)規(guī)劃算法實(shí)例詳解的文章就介紹到這了,更多相關(guān)python動態(tài)規(guī)劃算法是什么內(nèi)容請搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！