摘要：進一步訓練動規的基本套路.
1.正文：以前我沒有經過自省和學習，一直有誤以為動態規劃跟我們高中數學課上學的線性規劃有某種關聯，后來通過科學的敲打后逐漸明白了兩者就沒啥必然關系，若強行說它們有什么聯系，只能說公共點在于都是用于最優值求解上的，經典的動態規劃，很適用于計算機的計算上，一是通過大量重復的迭代操作求得收斂值就是計算機最擅長的操作,二是思路本身就帶有空間換時間的理念（線性表存盤計算結果可以復用），三是記憶體空間往往可以自行控制到最優（可以自己程式申請的記憶體空間，大小自己可控制，不像遞回等方法直接交由系統去做申請），以下通過幾道經典例題進階訓練一下，
復習一下：
（1）題意分析；
（2）基于分析數學建模；
（3）判定是否可以符合使用動規的兩大前置條件（最優子結構和無后效性），是則下一步，否則終止（非動規可以解決的問題，另尋他法）；
（4）動規基本三步曲：
1）結合題意根據模型選擇計算出比較合適的狀態轉移方程，歸約初始的狀態值，推匯出終止（最終收斂）條件；
2）迭代驗證；
3）選擇合適的迭代次序實作狀態轉移方程的迭代和收斂；
（5）編程實作，
2.題目：
子陣列：對于給定陣列a[0..n]，其中a[i..j]（0<=i<=j<=n）為該陣列的子陣列.
1.最大子陣列和問題:給定陣列a[0..n]求其所有子陣列中所有元素和最大的子陣列的元素和為多少？
2.最長公共子陣列問題：給定陣列a[0..n]和b[0..m]，求兩者公共子陣列中長度最長的子陣列的長度為多少？
3.輸入輸出示例：
1.最大子陣列和問題
輸入：
[-1, 2, 3, -2, 5]
輸出：
8
2.最長公共子陣列問題：
輸入：
[3, 2, 1, 4, 7]
[1, 2, 3, 2, 1]
輸出： 3
4.例程：
package algorithm.mathsolution;
/**
* @Project: taxet
* @Author: yh
* @Package: algorithm.mathsolution
* @Version: V1.0
* @Title: 分享經典的動態規劃問題（二）
* @Tag:
* @Description:
* 經典的子陣列類的動規問題
* 1.最大子陣列和問題
* 2.最長公共子陣列問題
* @Date: 2020/6/2 23:30
*/
public class SubArraySolution {
/**
* 1.最大子陣列和問題
* 1）顯然不需建模
* 2）根據題意分析所有情況得出最大值：
* 思路由淺入深：
* （1）顯然一個陣列的子陣列a[i,j]由i,j決定的，即有subArray = f(i,j)，最大值的直接定義為：max{sum(f(i,j))}
* （2）兩個自變數顯然要二重遍歷，考慮降維，重定義迭代子變數，考慮到可以通過歸類同一元素a[k]為末尾的子陣列為一個子范圍的最大值來得到整個陣列的最大值，有：
* a. max[k] = max[k - 1] > 0 ? max[k - 1] + a[k] : a[k];
* b. max{sum(f(i,j))} = max{max[k]}
* 邊界值推導：初始值顯然有max[i] = a[i]， 終止條件為一次正向遍歷到最后的元素，
* 其中max[k]是以a[k]為末尾元素的子陣列和的最大值，各個情況互斥的子范圍得到的和最大值比較必然得到整個陣列的最大子陣列和，
* 注意的是，雖然得到兩個子方程，但可以被認為狀態轉移方程的只有第一個，因為它才存在相鄰狀態（max[k],max[k - 1]）發生轉化的程序，
* 3）校驗：[1,2,3] =>
* 根據方程a有max[0] = 1， max[1] = max[0] + a[1] = 3, max[2] = max[1] + a[2] = 6
* 根據方程b有max = 6;(本身也是一個子陣列，符合預期結果)
* 4)編程實作，
* @param a
* @return
*/
private static long maxSumSubArraySum(int[] a) {
if (null == a) {
return -1;
}
long maxSum = 0L;
if (a.length == 0) {
return maxSum;
}
//構造被填的陣列
long[] max = new long[a.length];
//賦初始值
for (int i = 0; i < a.length; i++) {
max[i] = a[i];
}
//迭代狀態
maxSum = max[0];
for (int i = 1; i < max.length; i++) {
if (max[i - 1] > 0) {
max[i] += max[i - 1];
}
maxSum = Math.max(max[i], maxSum);
}
//回傳結果
return maxSum;
}
/**
* 2.最長公共子陣列問題
* 1)顯然也不用建模
* 2）根據題意分析出也是一個有兩個自變數，能不能像上面那樣直接通過重定義降維？
* 答案是：不能的，
* 首先要認識到“最長”的概念當然可以應用在一個資料結構的某種特征資料，
* 可是“公共”就意味著至少是兩個資料結構之間的特征資料了（當然本題只考慮兩個的情況，三個及其以上都是與此類推），
* 當然在某些都可以將兩個資料結構合并成一個以兩者間的某種特征資料作為陣列元素的陣列再做處理，也是一種思路，但至少這道題里不允許，
* 因為子陣列的定義與原有陣列的強關聯，一旦不在原有的資料結構操作，尋找子陣列將會是一個難題，
* 綜述，不能降維，否則成本會很大，
* 既然不降維，則顯然是二維的狀態轉移方程的常規尋找了，
* 繼續類似上題那樣定義max[i][j]：a[0 .. i]與b[0 .. j]的各自以a[i],b[j]為末尾元素的子陣列之間的最長公共子陣列長度，
* max[i][j]的迭代子可以有（max[i][j - 1], max[i - 1][j], max[i - 1][j - 1]），
* 可是根據題意“公共”的約束和max[i][j]的定義，max[i][j - 1]，max[i - 1][j]沒有考慮意義，只與max[i - 1][j - 1]，有方程：
* max[i][j] = a[i] == b[j] ? max[i - 1][j - 1] + 1 : 0;
* 3）校驗：
* 輸入：
* A: [1,2,3,2,1]
* B: [3,2,1,4,7]
* 輸出：
* 3
* 抽樣，顯然max[3][1] = 2；
* max[4][2] = 3 = max[3][1] + 1
* 4)編程實作
* @param a
* @param b
* @return
*/
private static int maxLenCommonSubArray(int[] a, int[] b) {
if (null == a || null == b) {
return -1;
}
int maxLen = 0;
if ((a.length | b.length) == 0) {
return maxLen;
}
int[][] max = new int[a.length][b.length];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < b.length; j++) {
if (a[i] == b[j]) {
max[i][j] = 1;
if (i > 0 && j > 0) {
max[i][j] += max[i - 1][j - 1];
}
}
maxLen = Math.max(maxLen, max[i][j]);
}
}
return maxLen;
}
public static void mainSum(String[] strings) {
int[] arr = {-1, 2, 3, -2, 5};
System.out.println(maxSumSubArraySum(arr));
}
public static void mainLen(String[] strings) {
int[] a = {1, 2, 3, 2, 1};
int[] b = {3, 2, 1, 4, 7};
System.out.println(maxLenCommonSubArray(a,b));
}
}
該題幫你建好模了，經典的例題，比較簡單，不再贅述，不懂的地方請認真看看注釋能否釋疑，有問題歡迎留言，
5.總結：
事實上，真正刷題的時候更應該的是發散思維去考慮更多的好解法而非只有動規的思路的，但博主希望近期就先把由淺至深的動規題都大致捋一遍再展開新方法的討論，所以對動規部分有問題可以盡早提出來，當然，要經過自己的思考再發問，之后哪怕別人也不知道或者其他情況獲取不到有效答案的，你也要自己開拓新的渠道尋找答案（博主常規解決方案），切忌自己主動放棄求知欲，不了了之，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/47553.html
標籤：其他
上一篇：UCF Local Programming Contest 2014 J. Factorial Products
下一篇：docker容器不能被外網訪問。