動态規劃
什麼是動态規劃？
動态規劃的大緻思路是把一個複雜的問題轉化成一個分階段逐漸遞推的過程，從簡單的初始狀态一步一步遞推，最終得到複雜問題的最優解。
基本思想與政策編輯:
由于動态規劃解決的問題多數有重疊子問題這個特點，為減少重複計算，對每一個子問題隻解一次，将其不同階段的不同狀态儲存在一個二維數組中。
1. 拆分問題： 根據問題的可能性把問題劃分成通過遞推或者遞歸一步一步實作。
關鍵就是這個步驟,動态規劃有一類問題就是從後往前推到,有時候我們很容易知道 : 如果隻有一種情況時,最佳的選擇應該怎麼做. 然後根據這個最佳選擇往前一步推導,得到前一步的最佳選擇
2. 定義問題狀态和狀态之間的關系： 用一種量化的形式表現出來,類似于高中學的推導公式,因為這種式子很容易用程式寫出來,也可以說對程式比較親和(也就是最後所說的狀态轉移方程式)
3. 動态規劃算法的基本思想與分治法類似，也是将待求解的問題分解為若幹個子問題(階段)，按順序求解子階段， 前一子問題的解，為後一子問題的求解提供了有用的資訊 。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丢棄其他局部解。依次解決各子問題，最後一個子問題就是初始問題的解。
我的了解是：比如我們找到最優解,我們應該講最優解儲存下來,為了往前推導時能夠使用前一步的最優解,在這個過程中難免有一些相比于最優解差的解,此時我們應該放棄, 隻儲存最優解 ,
這樣我們每一次都把最優解儲存了下來,大大降低了時間複雜度。
動态規劃解決問題的過程分為兩步：
1.尋找狀态轉移方程式
2.利用狀态轉移方程式自底向上求解問題
動态規劃原理
使用條件： 可分為多個相關子問題，子問題的解被重複使用
- 使用條件： 可分為多個相關子問題，子問題的解被重複使用
- Optimal substructure(優化子結構)：
- 一個問題的優化解包含了子問題的優化解
- 縮小子問題集合，隻需那些優化問題中包含的子問題，降低實作複雜性
- 我們可以自下而上的
- Subteties(重疊子問題)： 在問題的求解過程中，很多子問題的解将被多次使用。
- 動态規劃算法的設計步驟：分析優化解的結構遞歸地定義最優解的代價自底向上地計算優化解的代價儲存之，并擷取構造最優解的資訊根據構造最優解的資訊構造優化解
- 動态規劃特點：把原始問題劃分成一系列子問題；求解每個子問題僅一次，并将其結果儲存在一個表中，以後用到時直接存取，不重複計算，節省計算時間自底向上地計算。整體問題最優解取決于子問題的最優解(狀态轉移方程)(将子問題稱為狀态，最終狀态的求解歸結為其他狀态的求解)
最長公共子序列的動态規劃法實作
最長公共子序列(longest-common-subsequence, LCS)
(1)子序列：一個序列X ＝ x1x2...xn,中任意删除若幹項，剩餘的序列叫做A的一個子序列。也可以認為是從序列A按原順序保留任意若幹項得到的序列。
例如：對序列 1,3,5,4,2,6,8,7來說，序列3,4,8,7 是它的一個子序列。對于一個長度為n的序列，它一共有2^n 個子序列，有(2^n – 1)個非空子序列。在這裡需要提醒大家，子序列不是子集，它和原始序列的元素順序是相關的。
(2)公共子序列：如果序列Z既是序列X的子序列，同時也是序列Y的子序列，則稱它為序列X和序列Y的公共子序列。空序列是任何兩個序列的公共子序列。
(3)最長公共子序列：X和Y的公共子序列中長度最長的(包含元素最多的)叫做X和Y的最長公共子序列。
這個問題如果用窮舉法時間，最終求出最長公共子序列時，時間複雜度是Ο(2mn)，是指數級别的複雜度，對于長序列是不适用的。是以我們使用動态規劃法來求解。
刻畫最長公共子序列問題的最優子結構
設X=x 1 x 2 …x m 和Y=y 1 y 2 …y n 是兩個序列，Z=z 1 z 2 …z k 是這兩個序列的一個最長公共子序列。
1. 如果x m =y n ，那麼z k =x m =y n ，且Z k-1 是X m-1 ，Y n-1 的一個最長公共子序列；
2. 如果x m ≠y n ，那麼z k ≠x m ，意味着Z是X m-1 ，Y的一個最長公共子序列；
3. 如果x m ≠y n ，那麼z k ≠y n ，意味着Z是X，Y n-1 的一個最長公共子序列。
從上面三種情況可以看出，兩個序列的LCS包含兩個序列的字首的LCS。是以，LCS問題具有最優子結構特征。
遞歸的定義最優值
從最優子結構可以看出，如果x m =y n ，那麼我們應該求解X m-1 ，Y n-1 的一個LCS，并且将x m =y n 加入到這個LCS的末尾，這樣得到的一個新的LCS就是所求。
如果xm≠yn，我們需要求解兩個子問題，分别求X m-1 ，Y的一個LCS和X，Y n-1 的一個LCS。兩個LCS中較長者就是X和Y的一個LCS。
可以看出LCS問題具有重疊子問題性質。為了求X和Y的一個LCS，我們需要分别求出X m-1 ，Y的一個LCS和X，Y n-1 的一個LCS，這幾個字問題又包含了求出X m-1 ，Y n-1 的一個LCS的子子問題。(有點繞了。。。暈沒暈。。。。)
根據上面的分析，我們可以得出下面的公式；
計算最優解的值
根據上面的，我們很容易就可以寫出遞歸計算LCS問題的程式，通過這個程式我們可以求出各個子問題的LCS的值，此外，為了求解最優解本身，我們好需要一個表dp，dp[i，j]記錄使C[i，j]取值的最優子結構。
數組的填表過程
代碼實作：
package cn.itcast.recursion;public class LCS { public int findLCS(String A, String B) { int n = A.length(); int m = B.length(); //傳回一個字元數組，該字元數組中存放了目前字元串中的所有字元 //傳回的是字元數組char[]a char[] a = A.toCharArray(); char[] b = B.toCharArray(); //建立一個二維矩陣，用來推到公共子序列 int[][] dp = new int[n][m]; for (int i = 0; i < n; i++) { //如果找到第一列其中一個字元等于第一行第一個字元 if (a[i] == b[0]) { //找到第一列與第一行b[0]的相等的值，把其變成1 dp[i][0] = 1; //并将其後面的字元都變成1 for (int j = i + 1; j < n; j++) { dp[j][0] = 1; } break; } } for (int i = 0; i < m; i++) { //如果找到第一列其中一個字元等于第一行第一個字元 if (b[i] == a[0]) { //則把第一列後面的字元都變成1 dp[0][i] = 1; for (int j = i + 1; j < m; j++) { dp[0][j] = 1; } break; } } //從1開始是因為橫向和縱向下标為0的都周遊過了 for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { //橫向和縱向有相等的值 if (a[i] == b[j]) { //目前位置左邊的值+1 dp[i][j] = dp[i - 1][j - 1] + 1; } else { //取目前位置(左邊的值，上邊的值)的最大值 dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]); } } } for (int i = 0; i < n - 1; i++) { for (int j = 0; j < m; j++) { System.out.print(dp[i][j] + " "); } System.out.println(); } return dp[n - 1][m - 1]; } public static void main(String[] args) { LCS lcs = new LCS(); int findLCS = lcs.findLCS("android", "random"); System.out.println("最長子序列長度：" + findLCS); }}