题解 | #矩阵的最小路径和#

用dp方程实现矩阵的最小路径和。实现过程如下
1.创建一个n*m阶的矩阵dp，原点与原矩阵相同

    dp[0][0]=matrix[0][0];

2.分别给dp的第一列和第一行赋值

    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]; //第一行

3.dp方程

for (int i=1;i<n;i++)
    for (int j=1;j<m;j++) {
        //dp矩阵前一行与前一列的最小值与原矩阵对应点的值的和转换到dp矩阵当前点
        dp[i][j]=java.util.Math.min(dp[i-1,j],dp[i][j-1]) + matrix[i][j];     
    }

4.dp矩阵的末端左上角的的断电即为最小路径和

    return dp[n-1][m-1];

注：dp原点要初始化成原矩阵的原点；最终结果是dp矩阵端点(n-1,m-1)，而不是(n,m)；