摘要：延續首題優良傳統進一步探討和訓練一下動規的基本套路.
1.正文：其實，動態規劃作為運籌學的一個分支，經過前輩的理論沉淀，已經形成一套科學可行的解決思路，在實踐中借用前輩的智慧，結合實際問題我可以總結我在解決動規程序中常有的實作套路：
（1）題意分析；
（2）基于分析數學建模；
（3）判定是否可以符合使用動規的兩大前置條件（最優子結構和無后效性），是則下一步，否則終止（非動規可以解決的問題，另尋他法）；
（4）動規基本三步曲：
1）結合題意根據模型選擇計算出比較合適的狀態轉移方程，歸約初始的狀態值，推匯出終止（最終收斂）條件；
2）迭代驗證；
3）選擇合適的迭代次序實作狀態轉移方程的迭代和收斂；
（5）編程實作，
對待常規的動規問題，這樣的做法足矣，雖然沒有理論上那么嚴謹，表現在沒有過多的校驗或者數學推演，但須知我們本來就是為了解決現實問題而非理論問題，所以在面向工業實踐上的問題來看這樣的套路基本屬于嚴謹的范疇了，以下我逐步說明一下為何要做這樣的步驟：
步驟（1）：題意分析是大前提，如果這一步都做錯了，映射到解決業務需求的現實作業模型中你就是沒有跟產品對齊需求，理解錯了需求了，這樣做出來的產品還會有業務價值嗎？
步驟（2）：基于分析來建立數學模型，一是確保分析過后的正確理解作為建立數學模型的輸入引數，這樣一環扣一環，才會確保問題解決的正確性；二是必然，所有資訊化相關的實際問題終究是歸結于數學模型的建立，資訊的輸入輸出模型本質上就是可以映射成數學中自變數與因變數的函式變換，當然還有諸多特質注定它可以被數學建模解決，如果不分析你很難建模；如果不建模，你很難理解該如何推匯出合適狀態轉移方程，所以這一步是銜接；
步驟（3）：但凡想用任何一種技巧或方法去解決某類問題，都先校驗清楚該技巧或方法的適用范圍（無論是本次討論的動態規劃還是以后二分查找、分治法等等方法）是否符合題意場景，不然即便做出來也不能確保它的正確性；
步驟（4）：按著這三步曲走只是博主總結的個人實體，如上有問題，還請多多指教！
1）即便是一道題適用動態規劃，他也可以有種形式的狀態轉移方程（后面會討論），至于什么是合適的，除了具體問題具體分析外，還有結合方程是否可以轉化為方便編程實作的要素考慮；
2）驗證就不多說了，好比測驗驅動開發中的測驗步驟，必不可少的驗證其正確性的步驟，
3）至于選擇合適的迭代次序，博主踩過坑，有一次推匯出一個個性化的動規轉移方程上是需要按列逆向遍歷的二重遍歷，但沒理解到位，按常規的行正向遍歷次序去遍歷動規的存盤陣列，導致了迭代產生的資料都是不對的，通過除錯才發現，所以迭代計算的順序也是需要關注的，另外，確保動規的狀態轉移方程是可以收斂的，程式才不會死回圈，可收斂表現在可以根據引數推匯出迭代終止條件的，
步驟（5）不再贅述，關鍵在于組織好代碼即可，
不多說，看看今日有趣的例題，
2.題目：
某蛋糕店推出一種禮品卡，使用該卡可以用于購買店內的蛋糕，
每種蛋糕限購1個，
該卡片面值為R元，僅可以使用1次，結賬后卡內剩下的余額作廢，
已知店內的全部種類的蛋糕價格都為整數，
求出怎么購買，可使結賬后卡內剩下的余額最少？
3.輸入輸出示例：
輸入：
1）所有蛋糕的價值：
2, 3, 5, 11, 6
2）面值R：
15
輸出最少的余額：
1
4.例程：
public class Asolution {
/**
某蛋糕店推出一種禮品卡，使用該卡可以用于購買店內的蛋糕，
每種蛋糕限購1個，
該卡片面值為R元，僅可以使用1次，結賬后卡內剩下的余額作廢，
已知店內的全部種類的蛋糕價格都為整數，
求出怎么購買，可使結賬后卡內剩下的余額最少
*/
/**
* F[i][j]表示用j元面額買[0 .. i]內的蛋糕的最大金額
* F[i][j] = max{F[i - 1][j - a[i]] + a[i] , F[i - 1][j]}
*/
private static int getMaxValues(int[] prices, int r) {
int[][] maxs = new int[prices.length][r + 1];
int max = 0;
for (int j = 0; j <= r; j++) {
if (j >= prices[0]) {
maxs[0][j] = prices[0];
}
}
for (int i = 1; i < maxs.length; i++) {
for (int j = 0; j <= r; j++) {
maxs[i][j] = maxs[i - 1][j];
if (j >= prices[i]) {
maxs[i][j] = Math.max(maxs[i][j] , maxs[i - 1][j - prices[i]] + prices[i]);
}
if (max < maxs[i][j]) {
max = maxs[i][j];
}
}
}
return max;
}
public static void main(String[] strings) {
int[] prices = {2, 3, 5, 11, 6};
System.out.println(15 - getMaxValues(prices , 15));
}
}
現在按上述我自行總結的套路捋一遍：
該題比較淺顯，算是出題人已經幫你建好模了，不需要再抽象出來數學模型（變數都直接標注在題干里），
1.基于分析建模：問題最明顯：剩下余額最少，面值R固定，花費才是主動發生變化的變數，故我們可以轉化問題為求最大花費，即一個最優化問題，
1）它的未來狀態不會影響過去狀態（你將來花了多少錢都不會影響你過去實際已經花掉的最大值（是過去已經花掉的，不包含當前選擇花費多少的動態考慮）），無后效；
2）在子范圍內（n - 1個蛋糕）解決類似的問題得到的答案可以用于父范圍（n個蛋糕），屬于最優子結構，
2.三步走：
1） 顯然，狀態轉移方程很容易可以得出，分類討論一下即可：
（1）買了價值a[i]的蛋糕則：F[i - 1][j - a[i]] + a[i];
（2）不買價值a[i]的蛋糕則：F[i - 1][j]
兩者比較最大者勝出，這就”打擂臺“得到了最大花費了，
* F[i][j]表示用j元面額買[0 .. i]內的蛋糕的最大金額
* F[i][j] = max{F[i - 1][j - a[i]] + a[i] , F[i - 1][j]}
顯然，初始值F[0][j] =a[0]，終止條件是遍歷完成;
2）驗證：舉例如：求F[1][15],此時i=1，j=15
F[i - 1][j - a[i]] + a[i] = F[0][15 - 3] + 3 = a[0] + 3 = 5
F[i - 1][j] = F[0][15] = 2;
所以顯然是對的，當然還可以再驗證多幾個，不再贅述，
3）這里只要捋清楚遍歷次序就是了，因為初始值比較常規，就是首行，正向行遍歷即可，
5.總結：
1.雖然只是簡單的一道線性動規，但是捋清楚整個套路下來，我們就很容易聚焦到重點難點上：1）對于未曾建模的題型（后面會遇到），建模將會是難點，因為它是現實模型到數理模型的一個映射，焦點抓得好，建模才有效果；2）推導選擇出合適的狀態轉移方程，無他，唯訓練爾，當然，數學知識將會是很大的幫助，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/47550.html
標籤：其他
上一篇：tarjan演算法 求割點