5.5
这种题都差不多吖。弄一个flag，存起来
public class Solution { /** * @param grid: a list of lists of integers. * @return: An integer, minimizes the sum of all numbers along its path */ public int minPathSum(int[][] grid) { // write your code here int m = grid.length; int n = grid[0].length; int[][] flag = new int[m][n]; setFlag(grid,flag,m,n); /* for(int i = 0;i<m;i++){ for(int j =0;j<n;j++){ System.out.print(flag[i][j] + " "); } System.out.println(""); } */ return flag[0][0]; } public void setFlag(int[][] grid,int[][] flag,int m,int n){ flag[m-1][n-1] = grid[m-1][n-1]; for(int i = m-2;i >=0 ;i--){ flag[i][n-1] = flag[i+1][n-1] + grid[i][n-1]; } for(int i = n-2;i >=0 ;i--){ flag[m-1][i] = flag[m-1][i+1] + grid[m-1][i]; } for(int i = m-2;i >= 0;i--){ for(int j = n-2;j >= 0; j--){ flag[i][j] = grid[i][j] + Math.min(flag[i+1][j],flag[i][j+1]); } } } }