python programming training(四):动态规划
動態規劃,說白了類似于高中的數學歸納法。
?
- 遞推
- 核心:窮舉。減少共有狀態或路徑的重復計算。
目錄
1. 概念理解
1.1 使用動態規劃的條件
1.2 應用動態規劃的步驟
1.3 DP和貪心算法區別
1.4 DP和遞歸區別
1.4.1 斐波那契遞歸實現
1.4.2 斐波那契動態規劃實現
2. 分類
2.1 編號動態規劃-->最大不下降子序列
2.2 劃分動態規劃
2.3 數軸動態規劃:0-1背包問題
2.4 前綴動態規劃:最長公共子序列(LCS)
3. leedcode實戰案例
參考
??????????????
動態規劃(Dynamic Programming, DP)是運籌學的一個分支,是求解決策過程最優化的過程。美 R.Bellman在研究多階段決策過程的優化問題時,提出了著名的最優化原理,從而創立了動態規劃。
1. 概念理解
動態規劃可以簡單地理解為對傳統遞歸的一種優化。Dynamic Programming不是編程,而是決策。只是這種決策不是一下就出來的,而是一步步(multistage)積累出來。換句話說我們需要一個決策,但這個決策太大了,我們做不了,所以需要把他遞歸到我們可以簡單做出決策的狀態,然后從這些狀態開始,慢慢的“動態地”演進到最終的決策。
比如說用最少的硬幣換零錢?
突然和你說要換78分錢,你怎么就能迅速給出答案呢,你不能。但是如果是1分的話,你就可以,2分的話呢,就是在1分的基礎上再加1分,你也可以。于是你就慢慢地從1分開始一直算到78就有答案了。從另一個角度說,如果你用DP算出了怎么換78分,那如果我問你76分怎么換,你也應該有答案了。
所以,DP在實踐中很重要的就是遞推關系和邊界條件。
已知問題規模為n的前提A,求解一個未知解B。(我們用An表示“問題規模為n的已知條件”)
此時,如果把問題規模降到0,即已知A0,可以得到A0->B.
- 如果從A0添加一個元素,得到A1的變化過程。即A0->A1; 進而有A1->A2; A2->A3; …… ; Ai->Ai+1. 這就是嚴格的歸納推理,也就是我們經常使用的數學歸納法;
- 對于Ai+1,只需要它的上一個狀態Ai即可完成整個推理過程(而不需要更前序的狀態)。我們將這一模型稱為馬爾科夫模型。對應的推理過程叫做“貪心法”。
然而,Ai與Ai+1往往不是互為充要條件,隨著i的增加,有價值的前提信息越來越少,我們無法僅僅通過上一個狀態得到下一個狀態,因此可以采用如下方案:
- {A1->A2}; {A1, A2->A3}; {A1,A2,A3->A4};……; {A1,A2,...,Ai}->Ai+1. 這種方式就是第二數學歸納法。???????
- 對于Ai+1需要前面的所有前序狀態才能完成推理過程。我們將這一模型稱為高階馬爾科夫模型。對應的推理過程叫做“動態規劃法”。
上述兩種狀態轉移圖如下圖所示:
1.1 使用動態規劃的條件
該問題是否能用動態規劃解決的是可以分為多個相關子問題,這些”小問題“會不會被被重復調用。而不是一個“大問題”能夠被拆解為一堆“小問題”
舉個例子,有n個階梯,一個人每一步只能跨一個臺階或是兩個臺階,問這個人一共有多少種走法?
首先對這個問題進行抽象,n個階梯,每個階梯都代表一個“位置”,就像是圖論中的一個“點”,然后這n個不同位置之間會有一些橋梁把它們連接起來。==>也可以寫成列表形式,或鄰接矩陣。
idea:如果是暴力遍歷的話,從3到10的時候,你肯定會把5-10的可能路徑都算一遍,然后從4-10的時候,你又會把5-10的路徑算一遍,也就是重復計算了。
solve:創建一個數組a[],專門來存放位點x到10的所有可能路徑數。?
?a[5] = a[6] + a[7]
a[4] = a[5] + a[6] ? ? ? ? ? ? ? ? 數學歸納法?
.......
a[x] = a[x+1] + a[x+2]
我們發現在計算a[4]和a[5]的時候,都用到了a[6],也就是重復利用了結果。
==>換句話說,如果從6-10的最優路徑確定了,那無論是從3、4、5開始的路徑,凡是再次到達6,那么從6往后的最優路徑就不用再重復計算了。?
1.2 應用動態規劃的步驟
(1) 按順序從小到大計算。因為如果直接讓你計算f(11),你肯定一臉懵逼,但f(0), f(1)你卻能很快理解,發現規律
(2) 建立狀態轉移方程。求得f(n)表達式
(3) 緩存以往結果以復用。比如剛剛求得f(99),如果不將其緩存起來,那么求f(100)時,我們就必須重新從頭計算。?
1.3 DP和貪心算法區別
?貪心:如果第一步到H和I都可以,第二步到P和Q都可以,那我每一步只選最優,用貪心得到結果。<== 因為你要經歷的每個階段狀態跟決策無關,即每個階段狀態相互獨立,互不影響。
但現實情況是,你第一步的選擇會影響后面的分支。?
比如你第一步選擇H或I,但是到了H后,你就只能選擇經過P或Q到Z了,而如果到了I,你只能選擇R或S到Z。
這樣一來,即便第一步到H或I你選擇了較好的一條路,也不保證最終結果最優。?
==> 所以我們要把所有的路都嘗試一遍,才知道哪個最優。-->窮舉
但我們只需要計算到每個共有狀態的位置,求各階段的最優,最后每階段選最優組合貪心組合起來就行,因為共有狀態不影響決策,即不影響最終最優路徑選擇。對A->H->Q->Z和A->I->Q->Z,Q->Z是共有狀態。Q->Z的最優可減少每條經過Q的最優路徑的重復計算,當然可能存在A->H->Z路徑比任何一條經過Q的路徑更短,但我們說的是減少經過Q往后的路徑的重復計算。?
1.4 DP和遞歸區別
1.4.1 斐波那契遞歸實現
# 遞歸實現 def fib_re(n):if n < 2:return nelse:return fib_re(n-1) + fib_re(n-2)# 遞歸實現fib(100)時間太長,我出去打個電話都沒運算完,而動態規劃fib(100)秒算if __name__ == '__main__':result = fib_re(100)print(result)遞歸這種方式造成棧空間極大浪費!!!?
其指數級時間復雜度跟不能用沒啥區別!!!出個打個20分鐘的電話都沒結束
1.4.2 斐波那契動態規劃實現
# 動態規劃實現 def fib_DP(n):results = list(range(n+1))for i in range(n+1):if i < 2:results[i] = ielse:results[i] = results[i-1] + results[i-2]return results[n]if __name__ == '__main__':result = fib_DP(100)print(result)秒算?
2. 分類
2.1 編號動態規劃-->最大不下降子序列
2.2 劃分動態規劃
2.3 數軸動態規劃:0-1背包問題
2.4 前綴動態規劃:最長公共子序列(LCS)
3. leedcode實戰案例
舉個例子🌰,才是最好懂的學習方式
參考
[1] 知乎:如何理解動態規劃?
[2] 博客園:【算法復習】動態規劃
[3] CSDN:六大算法之三:動態規劃???????
總結
以上是生活随笔為你收集整理的python programming training(四):动态规划的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: python programming t
- 下一篇: 医学数据挖掘学习项目:他克莫司