題目描述
給定一個包含非負整數(shù)的 m x n 網(wǎng)格 grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。
說明：每次只能向下或者向右移動一步。
文章來源：http://www.zghlxwxcb.cn/news/detail-474768.html
思路
使用動態(tài)規(guī)劃的方法解決：文章來源地址http://www.zghlxwxcb.cn/news/detail-474768.html
- 路徑的方向只能是向下或向右
- 網(wǎng)格的第一行的每個元素只能從左上角元素開始向右移動到達，網(wǎng)格的第一列的每個元素只能從左上角元素開始向下移動到達，此時的路徑是唯一的，因此每個元素對應的最小路徑和即為對應的路徑上的數(shù)字總和
-
不在第一行和第一列的元素：以從其上方相鄰元素向下移動一步到達，或者從其左方相鄰元素向右移動一步到達，元素對應的最小路徑和等于
其上方相鄰元素與其左方相鄰元素兩者對應的最小路徑和中的最小值加上當前元素的值 - 圖例：此時是第一行和第一列；原始數(shù)組對應的dp數(shù)組是對應路徑上的數(shù)字綜合
- 如下，不在第一行和第一列；此時對應dp數(shù)組的元素為其上方相鄰元素與其左方相鄰元素兩者對應的最小路徑和中的最小值加上當前元素的值
6. 由以上分析可知，其方程如下：
代碼
class Solution {
public int minPathSum(int[][] grid) {
//如果grid數(shù)組為空
if(grid == null || grid.length == 0 || grid[0].length == 0){
return 0;
}
//獲取行列
int rows = grid.length,clumns = grid[0].length;
//創(chuàng)建目標數(shù)組
int[][] dp = new int[rows][clumns];
//為第一行第一列元素賦值
dp[0][0] = grid[0][0];
//在第一行時
for(int i=1;i<rows;i++){
dp[i][0] = dp[i-1][0] + grid[i][0];
}
//在第一列時
for(int j=1;j<clumns;j++){
dp[0][j] = dp[0][j-1] + grid[0][j];
}
//非第一行第一列
//循環(huán)行
for(int i=1;i<rows;i++){
//循環(huán)列
for(int j=1;j<clumns;j++){
//獲取最小的為目標數(shù)組當前元素的值
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
}
}
return dp[rows-1][clumns-1];
}
}
到了這里，關于64. 最小路徑和：給定一個包含非負整數(shù)的 m x n 網(wǎng)格 grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。 說明：每次只能向下或者向右移動一步。的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
