原理入門理論最優化原理問題求解模式實現思路狀態實現最長公共子序列湊硬幣

原理

入門理論

最優化原理

1951年美國數學家R．Bellman等人，根據一類多階段問題的特點，把多階段決策問題變換為一系列互相聯系的單階段問題，然后逐個加以解決。一些靜態模型，只要人為地引進“時間”因素，分成時段，就可以轉化成多階段的動態模型，用動態規劃方法去處理。與此同時，他提出了解決這類問題的“最優化原理”(PRinciple of optimality)：

“一個過程的最優決策具有這樣的性質：即無論其初始狀態和初始決策如何，其今后諸策略對以第一個決策所形成的狀態作為初始狀態的過程而言，必須構成最優策略”。簡言之，一個最優策略的子策略，對于它的初態和終態而言也必是最優的。

這個“最優化原理”如果用數學化一點的語言來描述的話，就是：假設為了解決某一優化問題，需要依次作出n個決策D1，D2，…，Dn，如若這個決策序列是最優的，對于任何一個整數k，1 < k < n，不論前面k個決策是怎樣的，以后的最優決策只取決于由前面決策所確定的當前狀態，即以后的決策Dk+1，Dk+2，…，Dn也是最優的。

最優化原理是動態規劃的基礎。任何一個問題，如果失去了這個最優化原理的支持，就不可能用動態規劃方法計算。能采用動態規劃求解的問題都需要滿足一定的條件： (1) 問題中的狀態必須滿足最優化原理； (2) 問題中的狀態必須滿足無后效性。 所謂的無后效性是指：“下一時刻的狀態只與當前狀態有關，而和當前狀態之前的狀態無關，當前的狀態是對以往決策的總結”。（這個感覺和馬爾科夫模型很像） (3) 子問題的重疊性 動態規劃將原來具有指數級時間復雜度的搜索算法改進成了具有多項式時間復雜度的算法。其中的關鍵在于解決冗余，這是動態規劃算法的根本目的。動態規劃實質上是一種以空間換時間的技術，它在實現的過程中，不得不存儲產生過程中的各種狀態，所以它的空間復雜度要大于其它的算法。

問題求解模式

　　　　　 初始狀態→│決策１│→│決策２│→…→│決策ｎ│→結束狀態 　　　　　 動態規劃決策過程示意圖 　　　　　

實現思路

動態規劃算法通?；谝粋€遞推公式及一個或多個初始狀態。 當前子問題的解將由上一次子問題的解推出。使用動態規劃來解題只需要多項式時間復雜度， 因此它比回溯法、暴力法等要快許多?，F在讓我們通過一個例子來了解一下DP的基本原理。首先，我們要找到某個狀態的最優解，然后在它的幫助下，找到下一個狀態的最優解。

最重要的就是確定動態規劃三要素： （1）問題的階段 （2）每個階段的狀態 （3）從前一個階段轉化到后一個階段之間的遞推關系。

確定了動態規劃的這三要素，整個求解過程就可以用一個最優決策表來描述，最優決策表是一個二維表，其中行表示決策的階段，列表示問題狀態，表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關系，從1行1列開始，以行或者列優先的順序，依次填寫表格，最后根據整個表格的數據通過簡單的取舍或者運算求得問題的最優解。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

舉個例子：

http://www.49028c.com/steven_oyj/archive/2010/05/22/1741374.html

實現思路有： 1.自頂向下(又稱記憶化搜索、備忘錄)：基本上對應著遞歸函數實現，從大范圍開始計算，要注意不斷保存中間結果，避免重復計算； 2.自底向上(遞推)：從小范圍遞推計算到大范圍； 動態規劃的重點：遞歸方程+邊界條件

動態規劃算法可以求解很多問題，比如矩陣乘法、最長公共子序列、構造最優二叉查找樹等，現就著名的最長公共子序列問題，采用動態規劃法分析之。

狀態

“狀態”用來描述該問題的子問題的解。

實現

最長公共子序列

子序列:若給定序列X={x1,x2,…,xm},則另一序列Z={z1,z2,…,zk},是X的子序列是指存在一個嚴格遞增下標序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有:zj=xij.

公共子序列:給定2個序列X和Y,當另一序列Z既是X的子序列又是Y的子序列時,稱Z是序列X和Y的公共子序列.

最長公共子序列:給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最長公共子序列.

如：序列ABCDEF和ADFGH的最長公共子序列為ADF

注意:最長公共子串(Longest Common Substirng)和最長公共子序列(Longest Common Subsequence,簡稱LCS)的區別為是最長公共子串的串是一個連續的部分,而最長公共子序列則是從不改變序列的順序,而從序列中去掉任意的元素而獲得新的序列;通俗的說就是子串中字符的位置必須是連續的而子序列則可以不必連續。

問題描述：給定2個序列X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A},找出X和Y的最長公共子序列

1.分析最優子結構性質：

設序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk} ,則

(1)若xm=yn,則zk=xm=yn,且z1,z2,…, zk-1是否為x1,x2,…,xm-1和y1,y2,…,yn-1的最長公共子序列.

(2)若xm≠yn且zk≠xm,則Z是x1,x2,…,xm-1和Y的最長公共子序列.

(3)若xm≠yn且zk≠yn,則Z是X和y1,y2,…,yn-1的最長公共子序列.

由此可見,2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列.因此,最長公共子序列問題具有最優子結構性質.當問題具有最優子結構性質和子問題重疊性質時就可以用動態規劃算法解決該問題.

2.由最長公共子序列問題的最優子結構性質建立子問題最優值的遞歸關系.用c[i][j]記錄序列和的最長公共子序列的長度.其中,Xi={x1,x2,…,xi},Yj={y1,y2,…,yj}.當i=0或j=0時,空序列是Xi和Yj的最長公共子序列.故此時C[i][j]=0.其它情況下,由最優子結構性質可建立遞歸關系如下: c[i][j]=?????0,c[i?1][j?1]+1,maxc[i?1][j],c[i][j?1],if i=0,j=0if x>0,y>0, xi>yjif i>0,j>0,xi≠yj  $$c[i][j] = /begin{cases}0, & /text{if $i = 0, j =0$} //c[i - 1][j - 1] + 1, & /text{if $x > 0, y >0$, $x_i > y_j$} //max{c[i-1][j], c[i][j-1]}, & /text{if $i > 0, j > 0, x_i /neq y_j$ }/end{cases}$$

http://www.2cto.com/kf/201611/565606.html http://m.codes51.com/article/detail_556679.html

湊硬幣

如果我們有面值為1元、3元和5元的硬幣若干枚，如何用最少的硬幣湊夠11元？ (表面上這道題可以用貪心算法，但貪心算法無法保證可以求出解，比如1元換成2元的時候)

首先我們思考一個問題，如何用最少的硬幣湊夠i元(i<11)？為什么要這么問呢？ 兩個原因：1.當我們遇到一個大問題時，總是習慣把問題的規模變小，這樣便于分析討論。 2.這個規模變小后的問題和原來的問題是同質的，除了規模變小，其它的都是一樣的， 本質上它還是同一個問題(規模變小后的問題其實是原問題的子問題)。

好了，讓我們從最小的i開始吧。當i=0，即我們需要多少個硬幣來湊夠0元。 由于1，3，5都大于0，即沒有比0小的幣值，因此湊夠0元我們最少需要0個硬幣。 (這個分析很傻是不是？別著急，這個思路有利于我們理清動態規劃究竟在做些什么。) 這時候我們發現用一個標記來表示這句“湊夠0元我們最少需要0個硬幣。”會比較方便， 如果一直用純文字來表述，不出一會兒你就會覺得很繞了。那么， 我們用d(i)=j來表示湊夠i元最少需要j個硬幣。于是我們已經得到了d(0)=0， 表示湊夠0元最小需要0個硬幣。當i=1時，只有面值為1元的硬幣可用， 因此我們拿起一個面值為1的硬幣，接下來只需要湊夠0元即可，而這個是已經知道答案的， 即d(0)=0。所以，d(1)=d(1-1)+1=d(0)+1=0+1=1。當i=2時， 仍然只有面值為1的硬幣可用，于是我拿起一個面值為1的硬幣， 接下來我只需要再湊夠2-1=1元即可(記得要用最小的硬幣數量)，而這個答案也已經知道了。 所以d(2)=d(2-1)+1=d(1)+1=1+1=2。一直到這里，你都可能會覺得，好無聊， 感覺像做小學生的題目似的。因為我們一直都只能操作面值為1的硬幣！ 讓我們看看i=3時的情況。當i=3時，我們能用的硬幣就有兩種了：1元的和3元的( 5元的仍然沒用，因為你需要湊的數目是3元！5元太多了親)。 既然能用的硬幣有兩種，我就有兩種方案。如果我拿了一個1元的硬幣，我的目標就變為了： 湊夠3-1=2元需要的最少硬幣數量。即d(3)=d(3-1)+1=d(2)+1=2+1=3。 這個方案說的是，我拿3個1元的硬幣；第二種方案是我拿起一個3元的硬幣， 我的目標就變成：湊夠3-3=0元需要的最少硬幣數量。即d(3)=d(3-3)+1=d(0)+1=0+1=1. 這個方案說的是，我拿1個3元的硬幣。好了，這兩種方案哪種更優呢？ 記得我們可是要用最少的硬幣數量來湊夠3元的。所以， 選擇d(3)=1，怎么來的呢？具體是這樣得到的：d(3)=min{d(3-1)+1, d(3-3)+1}。 我們要抽出動態規劃里非常重要的兩個概念：狀態和狀態轉移方程。

上文中d(i)表示湊夠i元需要的最少硬幣數量，我們將它定義為該問題的”狀態”， 這個狀態是怎么找出來的呢？我在另一篇文章 動態規劃之背包問題(一)中寫過： 根據子問題定義狀態。你找到子問題，狀態也就浮出水面了。 最終我們要求解的問題，可以用這個狀態來表示：d(11)，即湊夠11元最少需要多少個硬幣。 那狀態轉移方程是什么呢？既然我們用d(i)表示狀態，那么狀態轉移方程自然包含d(i)， 上文中包含狀態d(i)的方程是：d(3)=min{d(3-1)+1, d(3-3)+1}。沒錯， 它就是狀態轉移方程，描述狀態之間是如何轉移的。當然，我們要對它抽象一下，

d(i)=min{ d(i-vj)+1 }，其中i-vj >=0，vj表示第j個硬幣的面值。

偽代碼為：

參考鏈接：

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg http://www.hawstein.com/posts/dp-novice-to-advanced.html http://dev.21tx.com/2007/01/17/11010.html

動態規劃與貪婪算法的區別：

http://www.programgo.com/article/67512173783/ http://amp.itgo.me/a/3219840973004004279

動態規劃的教程算法以及源碼：

http://www.xuebuyuan.com/zt/4352330.html https://www.codechef.com/wiki/tutorial-dynamic-programming