題目:
示例:
分析:
給我們一個矩陣,我們需要找出一條路徑從矩陣第一層(索引為0)到達矩陣最后一層,并且使得路徑上的數(shù)值之和最小.
如果是老手,那么應(yīng)該一眼就能看出來可以使用動態(tài)規(guī)劃,如果看不出來,那我們接下來一起分析分析.
首先我們先不要搞這么復(fù)雜,以示例1為例,我們就假設(shè)矩陣只有兩層,先忽略掉第三層(最后一層):
那么我們從第一層到達最后一層(第二層)的最短路徑和是多少呢.
如果我到達的是第二層的6,那么我是可以從第一層的2和1兩個地方到達,所以我們?nèi)绻竭_的地方是6,則最短路徑和是1+6=7.
如果我到達的是第二層的5,那么可以從第一層的2和1和3一共三個地方到達,即到達第二層的5的最短路徑和為1+5=6.同理,到達第二層的4的最短路徑和為1+4=5.
所以如果是上述兩層的矩陣,我們得到的最短路徑和是5(從第一層到達最后一層的4).
我們現(xiàn)在再把第三層加入進來,是這樣的:
?和我們剛才只有兩層的矩陣相比,僅僅是多了一層,我們?nèi)匀豢梢蕴子脛偛诺挠嬎愎?現(xiàn)在我們把剛剛推導(dǎo)出來的到達第二層的最短路徑和覆蓋掉原始的數(shù)值,是這樣的:
?我們可以接著利用推導(dǎo)過的第二層來接著推導(dǎo)第三層,最后是這樣的:
?
所以我們遍歷最后推斷完畢的最后一層可以得出示例1的最小路徑和是13.
這類可以將大問題拆分成多個有關(guān)聯(lián)性的小問題的題目,我們都可以使用動態(tài)規(guī)劃.并且動態(tài)規(guī)劃大多離不開貪心思想.
根據(jù)以上思路我們不難寫出代碼,但是有一點需要注意一下,就是在遍歷矩陣每層的首位元素的時候要注意不能下標越界,具體可以參考下面的代碼.
完整代碼+結(jié)果如下:文章來源：http://www.zghlxwxcb.cn/news/detail-557525.html
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int n=matrix.size();
if(n==1) return matrix[0][0];
for(int i=1;i<n;i++){
//矩陣每行的開頭單獨拎出來,因為 0-1 會下標越界
matrix[i][0]+=min(matrix[i-1][0],matrix[i-1][1]);
for(int j=1;j<n-1;j++){
//找出上一層的最多相隔一列的最小路徑和,再與本層元素相加,得到本層的最小路徑和
matrix[i][j]+=min(min(matrix[i-1][j-1],matrix[i-1][j]),matrix[i-1][j+1]);
}
//矩陣每行的結(jié)尾也單獨拎出來,因為 n+1 會下標越界
matrix[i][n-1]+=min(matrix[i-1][n-1],matrix[i-1][n-2]);
}
int res=matrix[n-1][0];
//遍歷最后一層得出最小路徑和
for(int i=1;i<n;i++){
res=min(res,matrix[n-1][i]);
}
return res;
}
};
文章來源地址http://www.zghlxwxcb.cn/news/detail-557525.html
到了這里，關(guān)于力扣每日一題2023.7.13的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
