题目描述

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

示例1

输入
[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
返回值
12

思路

1. 这题的转移方程很好写，dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+matrix[i][j];
2. 但是在做这题时，我第一次没过。原以为将dp设置为[n+1][m+1]能够自动初始化最左列和最上行的数，没想到并不能做到。
3. 因此这题必须要首先初始化左列和上行。

code

import java.util.*;
public class Solution {
    public int minPathSum (int[][] matrix) {
        if(matrix==null || matrix.length==0)return 0;
        int n = matrix.length,m = matrix[0].length;
        int[][] dp = new int[n][m];
        dp[0][0]=matrix[0][0];
        for(int i=1;i<n;i++)dp[i][0] = dp[i-1][0]+matrix[i][0];
        for(int j=1;j<m;j++)dp[0][j] = dp[0][j-1]+matrix[0][j];
        for(int i=1;i<n;i++)
            for(int j=1;j<m;j++)
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+matrix[i][j];
        return dp[n-1][m-1];
    }
}