問(wèn)題：LeetCode第64題-求解最小路徑和
給定一個(gè)二維數(shù)組m行作煌，n列掘殴。假設(shè)這個(gè)二維數(shù)組中每個(gè)單元格的值都是正整數(shù)，表示從該單元格經(jīng)過(guò)時(shí)需要花費(fèi)的成本粟誓。
那么求從左上角第一個(gè)單元格到右下角最后一個(gè)單元格的路徑中奏寨，花費(fèi)的最小成本是多少？
約束條件為：每次只能向下或者向右移動(dòng)一步鹰服。
說(shuō)明：
給定一個(gè)m=3病瞳，n=3的二維數(shù)組cost揽咕，如下圖所示，從左上角的第一個(gè)單元格出發(fā)仍源，可以向右心褐，向下走，最終達(dá)到右下角笼踩。因?yàn)槁窂?1→3→1→1→1 的總和最小,所以輸出的結(jié)果為7
題解
- 暴力遞歸算法
- 記憶化搜索算法
- 二維動(dòng)態(tài)規(guī)劃算法
- 一維動(dòng)態(tài)規(guī)劃算法
1. 暴力遞歸
利用遞歸逗爹，對(duì)于每個(gè)元素我們考慮兩條路徑，向右走和向下走嚎于，在這兩條路徑中挑選路徑權(quán)值和較小的一個(gè)掘而。遞推公式如下：
cost(i,j) = grid[i][j] + min(cost(i+1,j),cost(i,j+1))
實(shí)現(xiàn)代碼如下：
/**
@name 暴力遞歸法
@brief
遞歸公式:
cost(i,j) = grid[i][j] + min(cost(i+1,j),cost(i,j+1))
以當(dāng)前點(diǎn)為原點(diǎn),依次向右和向下計(jì)算代價(jià)值
*/
int calculate(vector<vector<int>> &grid,int i,int j) {
size_t bound_m = grid.size(); //行
size_t bound_n = grid[0].size(); //列
if (i == bound_m || j == bound_n) return INT_MAX; //右邊界，下邊界
if (i == (bound_m -1) && j == (bound_n -1)) return grid[i][j]; //到目的地右下角直接返回
return grid[i][j] + min(calculate(grid, i+1, j), calculate(grid, i, j+1)); //遞歸查找最短路徑
}
int DPAlgorithm::minPathSum(vector<vector<int>> &grid) {
//從0,0點(diǎn)開(kāi)始出發(fā)
return calculate(grid, 0, 0);
}
復(fù)雜度以及優(yōu)化的點(diǎn)
復(fù)雜度
時(shí)間復(fù)雜度：O(2 m+n)于购。每次移動(dòng)最多可以有兩種選擇袍睡。
空間復(fù)雜度：O(m+n))。遞歸的深度是 m+n
優(yōu)化的點(diǎn)
當(dāng)我們從左上角(0,0)開(kāi)始出發(fā)的時(shí)候肋僧，因?yàn)橹荒苎刂?code>右和下2個(gè)方向斑胜，所以走1->3或者1->1,這樣依次走下去，必然會(huì)經(jīng)過(guò)2次5嫌吠，例如：1->3->5...以及1->1>5...止潘，可以想到，當(dāng)走的5的時(shí)候辫诅，5的走法也只有右和下2種走法凭戴，所以這樣就會(huì)造成從這個(gè)點(diǎn)出發(fā)到右下角(2,2)被計(jì)算了2次，如果這個(gè)矩陣很大的話(huà)炕矮，那么這樣的點(diǎn)就會(huì)有很多么夫，就會(huì)被重復(fù)很多次，時(shí)間復(fù)雜度不言而喻肤视。如何優(yōu)化档痪？
LeetCode提交結(jié)果：
2. 記憶化搜索算法
在暴力遞歸的基礎(chǔ)上進(jìn)行優(yōu)化，目的是將每次遞歸計(jì)算后的結(jié)果保存起來(lái)邢滑，下次遞歸計(jì)算的時(shí)候先去查表腐螟，檢查是否有保存過(guò)的計(jì)算結(jié)果，如果有直接返回殊鞭，如果沒(méi)有計(jì)算后更新表。
實(shí)現(xiàn)代碼如下：
//申請(qǐng)一張二維表
static vector<vector<int>> table;
int calculate2(vector<vector<int>> &grid,int i,int j) {
size_t bound_m = grid.size(); //行
size_t bound_n = grid[0].size(); //列
//判斷邊界
if (i == bound_m || j == bound_n) return INT_MAX;
//到達(dá)目的地尼桶，直接返回
if (i == (bound_m -1) && j == (bound_n -1)) return grid[i][j];
//查表操灿，不為空直接返回結(jié)果
if (table[i][j] != -1) return table[i][j];
//結(jié)果求和并存表
int sum = grid[i][j] + min(calculate2(grid, i+1, j), calculate2(grid, i, j+1));
table[i][j] = sum;
return sum;
}
int DPAlgorithm::minPathSum(vector<vector<int>> &grid) {
//從0,0點(diǎn)開(kāi)始出發(fā)
//暴力遞歸
// return calculate(grid, 0, 0);
// 記憶搜索算法
size_t m = grid.size(); //行
size_t n = grid[0].size(); //列
//初始化m*n表的大小以及內(nèi)容
table = vector<vector<int> >(m,vector<int> (n,-1));
return calculate2(grid, 0, 0);
}
復(fù)雜度以及優(yōu)化的點(diǎn)
復(fù)雜度
時(shí)間復(fù)雜度：O(mn)。
空間復(fù)雜度：O(mn)泵督。
優(yōu)化的點(diǎn)
通過(guò)使用記憶搜索算法進(jìn)行優(yōu)化趾盐，時(shí)間復(fù)雜度已經(jīng)被顯著的降低了，但空間復(fù)雜度卻顯著的增加了，為了進(jìn)一步降低算法的復(fù)雜度救鲤，我們繼續(xù)進(jìn)行優(yōu)化久窟。
LeetCode提交結(jié)果：
3. 二維動(dòng)態(tài)規(guī)劃算法
dp矩陣更新過(guò)程如下圖：新建一個(gè)額外的
dp矩陣，與原矩陣大小相同本缠。在這個(gè)矩陣中斥扛，dp(i,j)表示從左上角到[i,j]的最小路徑和。我們根據(jù)左上角的值丹锹，很容易初始化出第一行和第一列中 dp值對(duì)應(yīng)的原矩陣的值稀颁。然后根據(jù)初始化的值，去更新整個(gè)dp矩陣的值楣黍，對(duì)于每個(gè)元素[i,j]考慮其由左邊和上邊的值計(jì)算得出匾灶，因此獲得最小路徑有如下遞推公式：
dp(i,j)=grid(i,j) + min(dp(i-1,j),dp(i,j-1))
從上圖可以看到，當(dāng)我們初始化dp矩陣之后租漂，剩下的操作根據(jù)遞推公式依次填充每一行和每一列阶女，dp右下角便是我們要求的結(jié)果。
實(shí)現(xiàn)代碼如下：
int DPAlgorithm::minPathSum(vector<vector<int>> &grid) {
//從0,0點(diǎn)開(kāi)始出發(fā)
//暴力遞歸
// return calculate(grid, 0, 0);
// 記憶搜索算法
// size_t m = grid.size(); //行
// size_t n = grid[0].size(); //列
// //申請(qǐng)一張m*n的表
// table = vector<vector<int> >(m,vector<int> (n,-1));
// return calculate2(grid, 0, 0);
//二維dp算法
size_t m = grid.size(); //行
size_t n = grid[0].size(); //列
vector<vector<int>> dp(m,vector<int>(n,-1));
dp[0][0] = grid[0][0];
//更新第一行
for (int i = 1; i < n; i++) {
dp[0][i] = grid[0][i] + dp[0][i-1];
}
//更新第一列
for (int i = 1; i < m; i++) {
dp[i][0] = grid[i][0] + dp[i-1][0];
}
//根據(jù)遞推公式,按行更新dp表
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m-1][n-1];
}
復(fù)雜度以及優(yōu)化的點(diǎn)
復(fù)雜度
時(shí)間復(fù)雜度：O(mn)哩治，遍歷整個(gè)矩陣恰好一次秃踩。
空間復(fù)雜度：O(mn)，額外的一個(gè)同大小矩陣锚扎。
優(yōu)化的點(diǎn)
通過(guò)使用二維動(dòng)態(tài)規(guī)劃算法吞瞪，雖然可以解決這個(gè)問(wèn)題，但看起來(lái)時(shí)間復(fù)雜度以及空間復(fù)雜度和記憶搜索算法基本一樣驾孔，那是否有方法繼續(xù)優(yōu)化呢芍秆？
LeetCode提交結(jié)果：
4. 一維動(dòng)態(tài)規(guī)劃算法
通過(guò)分析二維動(dòng)態(tài)規(guī)劃算法，發(fā)現(xiàn)當(dāng)更新完第一行和第一列以后翠勉，每次都是一行一行的對(duì)dp矩陣的其他位置進(jìn)行更新妖啥，那么可不可以只用一個(gè)數(shù)組就完成對(duì)其他位置的更新呢？答案是可以的对碌！可以將一維數(shù)組理解為從上往下滾動(dòng)的數(shù)組荆虱。因?yàn)槲覀儾⒉魂P(guān)心中間的狀態(tài)是什么，只需要將這個(gè)數(shù)組滾動(dòng)到最后朽们，計(jì)算最后的結(jié)果值即可怀读。本題分析如下圖所示：
從圖中可以看到，一共滾動(dòng)了三次骑脱，第一次滾動(dòng)初始化dp數(shù)組菜枷，接下來(lái)每次借助二維數(shù)組和dp數(shù)組中的值對(duì)數(shù)組進(jìn)行滾動(dòng)更新，直到更新到最后一行（也就是本題的第三行）叁丧，最后一個(gè)標(biāo)紅的位置就是我們所求的結(jié)果啤誊。
實(shí)現(xiàn)代碼如下：
int DPAlgorithm::minPathSum(vector<vector<int>> &grid) {
//一維dp算法
size_t m = grid.size(); //行
size_t n = grid[0].size(); //列
vector<int> dp(n,-1);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
//更新第一個(gè)元素
dp[j] = grid[i][j];
} else if (i == 0 && j > 0) {
//更新第一行
dp[j] = grid[i][j] + dp[j-1];
} else if (j == 0 && i > 0) {
//更新第一列
dp[j] = grid[i][j] + dp[j];
} else {
//更新其他位置
dp[j] = grid[i][j] + min(dp[j-1], dp[j]);
}
}
}
return dp[n-1];
}
復(fù)雜度以及優(yōu)化的點(diǎn)
復(fù)雜度
時(shí)間復(fù)雜度 ：O(mn),遍歷整個(gè)矩陣恰好一次岳瞭。
空間復(fù)雜度 ：O(n)，額外的一維數(shù)組蚊锹，和一行大小相同
還能繼續(xù)優(yōu)化嗎瞳筏？
答案是可以的，可以將一維dp算法的思路應(yīng)用到二維dp算法上面牡昆。什么意思姚炕？因?yàn)槲覀冊(cè)谟?jì)算的過(guò)程中并不關(guān)心中間狀態(tài)，而只關(guān)系最后一行迁杨，所以钻心，我們可以免去申請(qǐng)二維dp矩陣，直接在給定的矩陣上進(jìn)行滾動(dòng)铅协，這樣捷沸，空間復(fù)雜度可以降為O(1)。但這樣會(huì)改變?cè)仃囍械闹岛罚枰鶕?jù)實(shí)際情況來(lái)使用痒给，本題是可以使用的。
