最小路径和

题目

64. 最小路径和
    给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

思路

使用动态规划来解决.自下而上解决.从右下方的点开始记录每个点的位置.

代码

class Solution {
    public int minPathSum(int[][] grid) {
        //使用动态规划来解决.自下而上解决.从右下方的点开始记录每个点的位置.
        int[] temp = new int[grid[0].length];
        for(int i = grid.length-1;i >= 0;i--){
            for(int j = grid[i].length-1;j>=0;j--){
                //有四种情况.主要区分是看累加值是从右边还是下边来
                //1.点在最右下方
                if(i == grid.length-1 && j == grid[i].length-1){
                    temp[j] = grid[i][j];
                }else 
                //2.点在下方边线
                if(i == grid.length-1 && j != grid[i].length-1){
                    temp[j] = grid[i][j] + temp[j+1];
                }else 
                //3.点在右方边线
                if(i != grid.length-1 && j == grid[i].length-1){
                    temp[j] = grid[i][j] + temp[j];
                }
                //4.点在其他位置.
                else {
                    temp[j] = grid[i][j] + Math.min(temp[j],temp[j+1]);
                }
            }
        }
        return temp[0];
    }
}