我們一路奮戰(zhàn)，
不是為了改變世界，
而是為了不讓世界改變我們。
目錄
我們一路奮戰(zhàn)，
不是為了改變世界，
而是為了不讓世界改變我們。
動態(tài)規(guī)劃——DP算法（Dynamic Programing）
一、??斐波那契數(shù)列（遞歸VS動態(tài)規(guī)劃）
1、??斐波那契數(shù)列——遞歸實現(xiàn)（python語言）——自頂向下
2、??斐波那契數(shù)列——動態(tài)規(guī)劃實現(xiàn)（python語言）——自底向上
二、??動態(tài)規(guī)劃算法——思想簡介
1、??DP算法思想
2、??DP算法——解決問題的基本特征
3、??DP算法——解決問題的基本步驟
?4、??求解例子——求階乘 n!
三、??動態(tài)規(guī)劃——常見例題
1、??求解最長不降子序列
2、??求解最長的公共子序列
獲取源碼？私信？關(guān)注？點贊？收藏？
動態(tài)規(guī)劃——DP算法（Dynamic Programing）
一、??斐波那契數(shù)列（遞歸VS動態(tài)規(guī)劃）
1、??斐波那契數(shù)列——遞歸實現(xiàn)（python語言）——自頂向下
遞歸調(diào)用是非常耗費內(nèi)存的，程序雖然簡潔可是算法復(fù)雜度為O(2^n)，當n很大時，程序運行很慢，甚至內(nèi)存爆滿。
def fib(n):
#終止條件，也就是遞歸出口
if n == 0 or n == 1:
return 1
else:
#遞歸條件
return (fib(n-1) + fib(n - 2))2、??斐波那契數(shù)列——動態(tài)規(guī)劃實現(xiàn)（python語言）——自底向上
動態(tài)規(guī)劃——將需要重復(fù)計算的問題保存起來，不需要下次重新計算。對于斐波那契數(shù)列，算法復(fù)雜度為O（n）。
def dp_fib(n):
#初始化一個數(shù)組，用于存儲記錄計算的結(jié)果。
res = [None] * (n + 1)
#前兩項設(shè)置為1。
res[0] = res[1] = 1
#自底向上，將計算結(jié)果存入數(shù)組內(nèi)。
for i in range(2, (n + 1)):
res[i] = res[i-1] + res[i-2]
return res[n]3、??方法概要
? ?。?）構(gòu)造一個公式，它表示一個問題的解是與它的子問題的解相關(guān)的公式：
（2）為這些子問題做索引，以便于它們能夠在表中更好的存儲與檢索（用數(shù)組存儲）。
（3）以自底向上的方法來填寫這個表格；首先填寫最小的子問題的解。
（4）這就保證了當我們解決一個特殊的子問題時，可以利用比它更小的所有可利用的子問題的解。
總之，因為在上世紀40年代（計算機普及很少時），這些規(guī)劃設(shè)計是與“列表”方法相關(guān)的，因此被稱為動態(tài)規(guī)劃——Dynamic Programing。
二、??動態(tài)規(guī)劃算法——思想簡介
1、??DP算法思想
? ?。?）將待求解的問題分解稱若干個子問題，并存儲子問題的解而避免計算重復(fù)的子問題，并由子問題的解得到原問題的解。
（2）動態(tài)規(guī)劃算法通常用于求解具有某種最有性質(zhì)的問題。
（3）動態(tài)規(guī)劃算法的基本要素：最優(yōu)子結(jié)構(gòu)性質(zhì)和重疊子問題。
最優(yōu)子結(jié)構(gòu)性質(zhì)：問題的最優(yōu)解包含著它的子問題的最優(yōu)解。即不管前面的策略如何，此后的決策必須是基于當前狀態(tài)（由上一次的決策產(chǎn)生）的最優(yōu)決策。
重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些問題被反復(fù)計算多次。對每個子問題只解一次，然后將其解保存起來，
以后再遇到同樣的問題時就可以直接引用，不必重新求解。
2、??DP算法——解決問題的基本特征
? ?。?）動態(tài)規(guī)劃一般求解最值（最優(yōu)、最大、最小、最長）問題；
（2）動態(tài)規(guī)劃解決?的問題一般是離散的，可以分解的（劃分階段的）。
（3）動態(tài)規(guī)劃結(jié)局的問題必須包含最優(yōu)子結(jié)構(gòu)，即可以有（n-1）的最優(yōu)推導(dǎo)出n的最優(yōu)。
3、??DP算法——解決問題的基本步驟
? 動態(tài)規(guī)劃算法的四個步驟：
?。?）刻畫最優(yōu)解的結(jié)構(gòu)特性。（一維、二維、三維數(shù)組）；
（2）遞歸的定義最優(yōu)解。（狀態(tài)轉(zhuǎn)移方程）
?。?）以自底向上的方法來計算最優(yōu)解。
（4）從計算得到的解來構(gòu)造一個最優(yōu)解。
?4、??求解例子——求階乘 n!
#遞歸實現(xiàn)求階乘
def multiply(n):
if n == 0 or n == 1:
return 1
return n * multiply(n -1)
#動態(tài)規(guī)劃實現(xiàn)求階乘
def dp_multiply(n):
temp = [None] * (n + 1)
temp[0] = 1
temp[1] = 1
for i in range(2, n + 1):
temp[i] = i * temp[i - 1]
return temp[n]三、??動態(tài)規(guī)劃——常見例題
1、??求解最長不降子序列
?。?）方法一：普通方法，算法復(fù)雜度為O（n^2）。
假設(shè)原始的數(shù)列為數(shù)組 a
分析：
刻畫結(jié)構(gòu)特性：用F[ i ]?表示前 i?項最長不下降子序列的長度；
狀態(tài)轉(zhuǎn)移方程：如果a [ i ] >=a [ j ],? F[i] = max(F[i],?F[j] + 1)? 其中，0 <= j < i
數(shù)據(jù)存儲：自底向上求解最小子結(jié)構(gòu)最優(yōu)解存入數(shù)組
?其中，pre[ i ]表示以元素a [ i ]?為結(jié)尾的最長不降序列的前一個元素索引（也就是以a[i]結(jié)尾的最長不降序列的倒數(shù)第二個元素）。存儲這個值是為了方便輸出最長的不降序列。
def Longest_Increaseing(a):
F = [1] * len(a)
pre = [0] * len(a)
for i in range(1, len(a)):
for j in range(i):
if a[i] >= a[j]:
F[i] = max(F[i], F[j] + 1)
pre[i] = j
return F, pre
a = [5,2,8,6,3,6,9,7]
F, pre = Longest_Increaseing(a)
#這里只是能獲得兩個數(shù)組，其中F[i]的最大值就是最長不降序列的長度。接下來，輸出最長的不降序列的元素值，請看下面的代碼：
2、??求解最長的公共子序列
?求解最長公共子序列代碼如下（python語言）：
import numpy as np
def LCS(str1, str2):
#獲取兩個序列的長度
m = len(str1)
n = len(str2)
#生成一個存儲計算子問題的二位矩陣，并將元素初始化為0。
#這個矩陣的尺寸比兩個序列的尺寸分別大1個單位。
#對于這個矩陣，第一行和第一列元素值必然為0。
#C[i][j]的含義是：Xi = （x1, x2, x3,..., xi）和Yj = （y1, y2, x3,..., yj）的最長公共子序列
C = np.zeros((m+1, n+1), dtype=int)
b = np.zeros((m+1, n+1), dtype=int)
for i in range(1, m+1):
for j in range(1, n+1):
#請注意這里為什么是i-1和j-1，因為其實C[1][1]表示的是
# 兩個序列的首個元素的最長公共子序列，對應(yīng)的是str1[0]和str2[0]
if str1[i-1] == str2[j-1]:
C[i][j] = C[i-1][j-1] + 1
b[i][j] = 1 #表示對角線方向
else:
if C[i][j-1] <= C[i-1][j]:
b[i][j] = 2 #表示朝上方向
else:
b[i][j] = 3 #表示朝左方向
C[i][j] = max(C[i][j-1], C[i-1][j])
return C, b
test1 = ['b', 'd','c', 'a', 'b', 'a']
test2 = ["a","b","c","b","d","a","b"]
a, b = LCS(test2, test1)
print(a)
#矩陣a存儲的是公共子序列的長度，最大值就是最大公共子序列的長度
[[0 0 0 0 0 0 0]
[0 0 0 0 1 1 1]
[0 1 1 1 1 2 2]
[0 1 1 2 2 2 2]
[0 1 1 2 2 3 3]
[0 1 2 2 2 3 3]
[0 1 2 2 3 3 4]
[0 1 2 2 3 4 4]]
print(b)
#這里： 1表示對角線方向、2表示朝上、3表示朝左，主要是為了求具體的子序列用的。
[[0 0 0 0 0 0 0]
[0 2 2 2 1 3 1]
[0 1 3 3 2 1 3]
[0 2 2 1 3 2 2]
[0 1 2 2 2 1 3]
[0 2 1 2 2 2 2]
[0 2 2 2 1 2 1]
[0 1 2 2 2 1 2]]
?接下來是輸出最長公共子序列：
import numpy as np
def LCS(str1, str2):
#獲取兩個序列的長度
m = len(str1)
n = len(str2)
#生成一個存儲計算子問題的二位矩陣，并將元素初始化為0。
#這個矩陣的尺寸比兩個序列的尺寸分別大1個單位。
#對于這個矩陣，第一行和第一列元素值必然為0。
#C[i][j]的含義是：Xi = （x1, x2, x3,..., xi）和Yj = （y1, y2, x3,..., yj）的最長公共子序列
C = np.zeros((m+1, n+1), dtype=int)
b = np.zeros((m+1, n+1), dtype=int)
for i in range(1, m+1):
for j in range(1, n+1):
#請注意這里為什么是i-1和j-1，因為其實C[1][1]表示的是
# 兩個序列的首個元素的最長公共子序列，對應(yīng)的是str1[0]和str2[0]
if str1[i-1] == str2[j-1]:
C[i][j] = C[i-1][j-1] + 1
b[i][j] = 1 #表示對角線方向
else:
if C[i][j-1] <= C[i-1][j]:
b[i][j] = 2 #表示朝上方向
else:
b[i][j] = 3 #表示朝左方向
C[i][j] = max(C[i][j-1], C[i-1][j])
return C, b
def Print_Lcs(b, X, i , j):
if i == 0 or j == 0:
return
if b[i][j] == 1:
Print_Lcs(b, X, i-1, j-1)
print(X[i-1]) #為什么是i-1，因為b矩陣的行比X的行長一個單位，而且只輸出相等的值，表示公共元素。
elif b[i][j] == 2:
Print_Lcs(b, X, i-1, j)
else:
Print_Lcs(b, X, i, j-1)
if __name__ == '__main__':
test1 = ['b', 'd','c', 'a', 'b', 'a']
test2 = ["a","b","c","b","d","a","b"]
a, b = LCS(test2, test1)
Print_Lcs(b, test2, 7, 6)
#輸出的結(jié)果是: b、c、b、a 。(請注意這里結(jié)果不唯一，因為最長子序列長度為4， 存在三個序列長度為4的子序列)
好了，這篇博客到這就結(jié)束了，感謝大家的閱讀！
2023年第二十九期，希望得到大家的喜歡???
也是新的系列，將會持續(xù)更新，???
希望大家有好的意見或者建議，歡迎私信
以上就是本篇文章的全部內(nèi)容了
?~ 關(guān)注我，點贊博文~ 每天帶你漲知識!
1.看到這里了就 [點贊+好評+收藏] 三連 支持下吧，你的「點贊，好評，收藏」是我創(chuàng)作的動力。
2.關(guān)注我 ~ 每天帶你學習 :各種前端插件、3D炫酷效果、圖片展示、文字效果、以及整站模板 、HTML模板 、C++、數(shù)據(jù)結(jié)構(gòu)、Python程序設(shè)計、Java程序設(shè)計、爬蟲等！?「在這里有好多 開發(fā)者，一起探討 前端 開發(fā)?知識，互相學習」！
3.以上內(nèi)容技術(shù)相關(guān)問題可以相互學習，可 關(guān) 注 ↓公 Z 號 獲取更多源碼 !
?
獲取源碼？私信？關(guān)注？點贊？收藏？
??+??+??+???文章來源：http://www.zghlxwxcb.cn/news/detail-691987.html
有需要源碼的小伙伴可以 關(guān)注下方微信公眾號 " Enovo開發(fā)工廠 "???文章來源地址http://www.zghlxwxcb.cn/news/detail-691987.html
到了這里，關(guān)于?Python—數(shù)據(jù)結(jié)構(gòu)與算法?---動態(tài)規(guī)劃—DP算法（Dynamic Programing）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
