1.題目描述
2.思路
（1）dp[i][j] 表示從起點 (0,0) 走到位置 (i,j) 的最小路徑和
（2）對于位置 (i, j)，只能從 上面 (i-1,j) 或 左邊 (i,j-1) 走過來，所以：
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
當前格子總路徑和 = 當前格子的值 + 從上或左走過來的最小路徑和
（3）初始化，從起點到起點的路徑和（只有這一個格子），要“消耗”這個格子的值了，所以路徑和初始就是 1。
起點：dp[0][0] = grid[0][0]
第一行只能從左邊走來：
dp[0][j] = dp[0][j-1] + grid[0][j]; // for j in 1…n-1
第一列只能從上面走來：
dp[i][0] = dp[i-1][0] + grid[i][0]; // for i in 1…m-1
（4）遍歷順序：
必須從上到下、從左到右，因為 dp[i][j] 依賴于 dp[i-1][j] 和 dp[i][j-1]。
3.代碼實現
class Solution {public int minPathSum(int[][] grid) {//行數，grid[m][n]是存儲最小數據和的數據int m=grid.length;//列數int n=grid[0].length;if(m==0||n==0){//只有一行或者一列的情況，不滿足找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。return 0;}//向右走，進行數組初始化，初始化第一行,也就是列數n會增加for(int j=1;j<n;j++){//因為是求最小路徑和，當前元素的值，等于他左邊元素加上當前元素的值grid[0][j]=grid[0][j]+grid[0][j-1];}//向下走，初始化第一列for(int i=1;i<m;i++){grid[i][0]=grid[i][0]+grid[i-1][0];}for(int j=1;j<n;j++){//每次只能向右走for(int i=1;i<m;i++){//每次只能向下走grid[i][j]=grid[i][j]+Math.min(grid[i-1][j],grid[i][j-1]);}}return grid[m-1][n-1];}
}
)
