题意整理

• 给定一个$n\ast mn*m$大小矩阵，每个单元格有一个数字。
• 求从左上角单元格出发，走到右下角时最短的路径和。

方法一（动态规划）

1.解题思路

• 状态定义：$dp[i][j]dp[i][j]$表示从起点走到$\mathrm{（}i,j\mathrm{）}（i,j）$位置的最小路径和。
• 状态初始化：走到起点位置的路径和等于矩阵中该点的数字的值，即$dp[0][0]=matrix[0][0]dp[0][0]=matrix[0][0]$。
• 状态转移：第0列的路径只能由前一行向下走得到，所以$dp[i][0]=dp[i-1][0]+matrix[i][0]dp[i][0]=dp[i-1][0]+matrix[i][0]$。第0行的路径只能由前一列向右走得到，所以$dp[0][j]=dp[0][j-1]+matrix[0][j]dp[0][j]=dp[0][j-1]+matrix[0][j]$。其它位置，要么向右，要么向下，取较小者，所以$dp[i][j]=Math\mathrm{.}min(dp[i-1][j],dp[i][j-1])+matrix[i][j]dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+matrix[i][j]$。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        //矩阵的行数n和列数m
        int n=matrix.length;
        int m=matrix[0].length;
        //定义dp数组，dp[i][j]表示从起点走到（i,j）位置的最小路径和
        int[][] dp=new int[n][m];
        //初始化起点位置
        dp[0][0]=matrix[0][0];
        //第0列的路径只能由前一行向下走得到
        for(int i=1;i<n;i++){
            dp[i][0]=dp[i-1][0]+matrix[i][0];
        }
        //第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];
    }
}

3.复杂度分析

• 时间复杂度：状态转移过程中，两层循环，总共执行$(n-1)\ast (m-1)(n-1)*(m-1)$次，所以时间复杂度为$O(n\ast m)O(n*m)$。
• 空间复杂度：需要额外大小为$n\ast mn*m$的dp数组，所以空间复杂度是$O(n\ast m)O(n*m)$。

方法二（原地替换）

1.解题思路

思路和方法一差不多。不过不需要额外定义dp数组，直接使用原矩阵来表示起点到某个目标点的最小路径和，由于只能向下或向右移动，不会出现重复计算的情况，所以可以用原数组存储对应的路径和。

图解展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        //矩阵的行数n和列数m
        int n=matrix.length;
        int m=matrix[0].length;
        //第0列的路径只能由前一行向下走得到
        for(int i=1;i<n;i++){
            matrix[i][0]+=matrix[i-1][0];
        }
        //第0行的路径只能由前一列向右走得到
        for(int j=1;j<m;j++){
            matrix[0][j]+=matrix[0][j-1];
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                //要么向右，要么向下，取较小者
                matrix[i][j]+=Math.min(matrix[i-1][j],matrix[i][j-1]);
            }
        }
        return matrix[n-1][m-1];
    }
}

3.复杂度分析

• 时间复杂度：状态转移过程中，两层循环，总共执行$(n-1)\ast (m-1)(n-1)*(m-1)$次，所以时间复杂度为$O(n\ast m)O(n*m)$。
• 空间复杂度：需要额外常数级别的空间，所以空间复杂度是$O(1)O(1)$。