python動態(tài)規(guī)劃算法實例詳解

更新時間：2020年11月22日 11:03:19 作者：十一

在本篇文章里小編給大家整理了關(guān)于python動態(tài)規(guī)劃算法實例內(nèi)容，有需要的朋友們可以參考學(xué)習(xí)下。

如果大家對這個生僻的術(shù)語不理解的話，那就先聽小編給大家說個現(xiàn)實生活中的實際案例吧，雖然現(xiàn)在手機是相當(dāng)?shù)谋憬?，還可以付款，但是最初的時候，我們經(jīng)常會使用硬幣，其中，我們?nèi)绻龅绞种杏泻芏辔迕蛘?塊錢硬幣，要怎么湊出來5元錢呢？這么一個過程也可以稱之為動態(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 項

代碼如下：

# _*_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) = 1
f(2) = 1
f(3) = f(1) + f(2) = 1+ 1 = 2
f(4) = f(3) + f(2) = 2 + 1 = 3
...
f(n) = f(n-1) + f(n-2)

實例擴展：

爬樓梯

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

解析：

如果給的兩個示例看的不是特別清楚，你可以當(dāng)階梯為0，那么上樓梯方法0種這是必然，當(dāng)階梯只有1那么上樓梯方法只有1種：
當(dāng)4個臺階：
輸入：4
輸出：4
1. 1階 + 1階 + 1階 + 1階
2. 2階 + 2階
3. 1階 + 2階 + 1階
4. 2階 + 1階 + 1階
5. 1階 + 1階 + 2階
那么得到：
階梯數(shù) 爬樓梯方法
0 0
1 1
2 2
3 3
4 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 c
obj = Solution()
result = obj.climbStairs(8)

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

您可能感興趣的文章: