動態規劃
什么是動態規劃？
動態規劃的大致思路是把一個復雜的問題轉化成一個分階段逐步遞推的程序，從簡單的初始狀態一步一步遞推，最終得到復雜問題的最優解，
基本思想與策略編輯:
由于動態規劃解決的問題多數有重疊子問題這個特點，為減少重復計算，對每一個子問題只解一次，將其不同階段的不同狀態保存在一個二維陣列中，
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=x1x2…xm和Y=y1y2…yn是兩個序列，Z=z1z2…zk是這兩個序列的一個最長公共子序列，
1. 如果xm=yn，那么zk=xm=yn，且Zk-1是Xm-1，Yn-1的一個最長公共子序列；
2. 如果xm≠yn，那么zk≠xm，意味著Z是Xm-1，Y的一個最長公共子序列；
3. 如果xm≠yn，那么zk≠yn，意味著Z是X，Yn-1的一個最長公共子序列，
從上面三種情況可以看出，兩個序列的LCS包含兩個序列的前綴的LCS，因此，LCS問題具有最優子結構特征，
遞回的定義最優值
從最優子結構可以看出，如果xm=yn，那么我們應該求解Xm-1，Yn-1的一個LCS，并且將xm=yn加入到這個LCS的末尾，這樣得到的一個新的LCS就是所求，
如果xm≠yn，我們需要求解兩個子問題，分別求Xm-1，Y的一個LCS和X，Yn-1的一個LCS，兩個LCS中較長者就是X和Y的一個LCS，
可以看出LCS問題具有重疊子問題性質，為了求X和Y的一個LCS，我們需要分別求出Xm-1，Y的一個LCS和X，Yn-1的一個LCS，這幾個字問題又包含了求出Xm-1，Yn-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);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/116912.html
標籤：其他