前言
上一節(jié)通過兩個(gè)經(jīng)理案例初步認(rèn)識(shí)動(dòng)態(tài)規(guī)劃颤诀，今天這一節(jié)主要講動(dòng)態(tài)規(guī)劃的理論知識(shí)。
“一個(gè)模型三個(gè)特征”理論講解
實(shí)際上，動(dòng)態(tài)規(guī)劃作為一個(gè)非常成熟的算法思想温亲，這部分理論總結(jié)為“一個(gè)模型三個(gè)特征”。
一個(gè)模型
一個(gè)模型指動(dòng)態(tài)規(guī)劃適合解決的問題模型杯矩。這個(gè)模型定義為“多階段決策最優(yōu)解模型”栈虚。
一般是用動(dòng)態(tài)規(guī)劃來解決最優(yōu)問題。而解決問題的過程史隆，需要經(jīng)歷多個(gè)決策階段魂务。每個(gè)決策階段都對(duì)應(yīng)著一組狀態(tài)。然后尋找一組決策序列泌射，經(jīng)過這組決策序列粘姜，能夠產(chǎn)生最終期望求解的值。
三個(gè)特征
三個(gè)特征分別是：最優(yōu)子結(jié)構(gòu)熔酷、無后效性和重復(fù)子問題孤紧。
- 最優(yōu)子結(jié)構(gòu)：?jiǎn)栴}的最優(yōu)解包含子問題的最優(yōu)解。
- 無后效性：有兩層含義拒秘。
- 第一層号显，在推導(dǎo)后面階段的狀態(tài)時(shí)，只關(guān)心前面階段的狀態(tài)值翼抠。
- 第二層咙轩，某階段的狀態(tài)一旦確定，就不受之后階段的決策影響阴颖。
- 重復(fù)子問題：不同的決策序列活喊，到達(dá)某個(gè)相同的階段時(shí)，可能會(huì)產(chǎn)生重復(fù)的狀態(tài)量愧。
兩種動(dòng)態(tài)規(guī)劃解題思路總結(jié)
解決動(dòng)態(tài)規(guī)劃問題钾菊，一般有兩種思路。分別是狀態(tài)轉(zhuǎn)移表法和狀態(tài)轉(zhuǎn)移方程法偎肃。
狀態(tài)轉(zhuǎn)移表法
狀態(tài)轉(zhuǎn)移表法的解題思路概括為：回溯算法實(shí)現(xiàn)-定義狀態(tài)-畫遞歸樹-找重復(fù)子問題-畫狀態(tài)轉(zhuǎn)移表-根據(jù)遞推關(guān)系填表-將填表過程翻譯成代碼煞烫。
我們來看一下，如何套用狀態(tài)轉(zhuǎn)移表法來解決動(dòng)態(tài)規(guī)劃問題累颂。
假設(shè)我們有一個(gè)n乘以n的矩陣w[n][n]滞详。矩陣存儲(chǔ)的都是正整數(shù)凛俱。棋子起始位置在左上角，終止位置在右下角料饥。那從左上角移動(dòng)到右下角的最短路徑長(zhǎng)度是多少蒲犬？
回溯算法實(shí)現(xiàn)
public class Solution {
private int minDist = int.MaxValue;
public int MinDist { get { return minDist; } }
// 調(diào)用方式：MinDistBT(0, 0, 0, w, n);
public void MinDistBT (int i, int j, int dist, int[][] w, int n) {
// 到達(dá)n-1, n-1這個(gè)位置了
if (i == n - 1 && j == n - 1) {
dist = dist + w[i][j];
if (dist < minDist) minDist = dist;
return;
}
if (i < n - 1) { // 往下走，更新i=i+1, j=j
MinDistBT (i + 1, j, dist + w[i][j], w, n);
}
if (j < n - 1) { // 往右走岸啡，更新i=i, j=j+1
MinDistBT (i, j + 1, dist + w[i][j], w, n);
}
}
}
定義狀態(tài)
從回溯代碼的函數(shù)調(diào)用可知原叮，每一個(gè)狀態(tài)包含三個(gè)變量(i, j, dist)，其中 i巡蘸，j 分別表示行和列奋隶，dist 表示從起點(diǎn)到達(dá)(i, j)的路徑長(zhǎng)度。
畫遞歸樹
有了回溯代碼和狀態(tài)定義悦荒，把每個(gè)狀態(tài)作為一個(gè)節(jié)點(diǎn)唯欣，畫出遞歸樹。
找重復(fù)子問題
從上圖可知搬味，存在重復(fù)子問題黍聂。
畫狀態(tài)轉(zhuǎn)移表
我們畫出一個(gè)二維狀態(tài)表，表中的行身腻、列表示棋子所在的位置产还，表中的數(shù)值表示從起點(diǎn)到這個(gè)位置的最短路徑。
根據(jù)遞推關(guān)系填表
按照決策過程嘀趟，通過不斷狀態(tài)遞推演進(jìn)脐区，將狀態(tài)表填好。
將填表過程翻譯成代碼
public class Solution2 {
public int MinDistDP (int[][] matrix, int n) {
int[][] states = new int[n][];
for (int i = 0; i < n; i++) {
states[i] = new int[n];
}
int sum = 0;
for (int j = 0; j < n; ++j) { // 初始化states的第一行數(shù)據(jù)
sum += matrix[0][j];
states[0][j] = sum;
}
sum = 0;
for (int i = 0; i < n; ++i) { // 初始化states的第一列數(shù)據(jù)
sum += matrix[i][0];
states[i][0] = sum;
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j < n; ++j) {
states[i][j] = matrix[i][j] + Math.Min (states[i][j - 1], states[i - 1][j]);
}
}
return states[n - 1][n - 1];
}
}
狀態(tài)轉(zhuǎn)移方程法
狀態(tài)轉(zhuǎn)移方程法的解題思路概括為：找最優(yōu)子結(jié)構(gòu)-寫狀態(tài)轉(zhuǎn)移方程-將狀態(tài)轉(zhuǎn)移方程翻譯成代碼她按。
還是拿上面的例子來說明牛隅。
找最優(yōu)子結(jié)構(gòu)
min_dist(i, j)可以通過min_dist(i, j-1)和min_dist(i-1, j)兩個(gè)狀態(tài)推導(dǎo)出來，符合“最優(yōu)子結(jié)構(gòu)”酌泰。
寫狀態(tài)轉(zhuǎn)移方程
min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))
強(qiáng)調(diào)一下媒佣，狀態(tài)轉(zhuǎn)移方程是解決動(dòng)態(tài)規(guī)劃的關(guān)鍵。
將狀態(tài)轉(zhuǎn)移方程翻譯成代碼
一般情況下陵刹，有兩種代碼實(shí)現(xiàn)方法：
- 遞歸+“備忘錄”
- 迭代遞推
用遞歸+“備忘錄”將狀態(tài)轉(zhuǎn)移方程翻譯成代碼默伍。
public class Solution3 {
private int[, ] matrix = new int[4, 4] { { 1, 3, 5, 9 }, { 2, 1, 3, 4 }, { 5, 2, 6, 7 }, { 6, 8, 4, 3 } };
private int n = 4;
private int[, ] mem = new int[4, 4];
public int MinDist (int i, int j) { // 調(diào)用MinDist(n-1, n-1)
if (i == 0 && j == 0) return matrix[0, 0];
if (mem[i, j] > 0) return mem[i, j];
int minLeft = int.MaxValue;
if (j - 1 >= 0) {
minLeft = MinDist (i, j - 1);
}
int minUp = int.MaxValue;
if (i - 1 >= 0) {
minUp = MinDist (i - 1, j);
}
int curMinDist = matrix[i, j] + Math.Min (minLeft, minUp);
mem[i, j] = curMinDist;
return curMinDist;
}
}
總結(jié)
動(dòng)態(tài)規(guī)劃有兩種解題思路：狀態(tài)轉(zhuǎn)移表法和狀態(tài)轉(zhuǎn)移方程法。
狀態(tài)轉(zhuǎn)移表法的解題思路概括為：回溯算法實(shí)現(xiàn)-定義狀態(tài)-畫遞歸樹-找重復(fù)子問題-畫狀態(tài)轉(zhuǎn)移表-根據(jù)遞推關(guān)系填表-將填表過程翻譯成代碼衰琐。
狀態(tài)轉(zhuǎn)移方程法的解題思路概括為：找最優(yōu)子結(jié)構(gòu)-寫狀態(tài)轉(zhuǎn)移方程-將狀態(tài)轉(zhuǎn)移方程翻譯成代碼也糊。
