動(dòng)態(tài)規(guī)劃算法如何在python項(xiàng)目中實(shí)現(xiàn)

動(dòng)態(tài)規(guī)劃算法如何在python項(xiàng)目中實(shí)現(xiàn)？針對(duì)這個(gè)問(wèn)題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問(wèn)題的小伙伴找到更簡(jiǎn)單易行的方法。

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

練習(xí)：使用遞歸和非遞歸的方法來(lái)求解斐波那契數(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) = 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í)例擴(kuò)展：

爬樓梯

假設(shè)你正在爬樓梯，需要n階才能到達(dá)樓頂
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 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è)臺(tái)階：
輸入：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
...
如果感覺(jué)看的不明顯可以推理一下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%的人。通過(guò)優(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)于動(dòng)態(tài)規(guī)劃算法如何在python項(xiàng)目中實(shí)現(xiàn)問(wèn)題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒(méi)有解開(kāi)，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識(shí)。