NC59：矩阵的最小路径和

解法1：暴力递归：

因为是从左上角到右下角，只能向右或者向下，

• 可以使用递归，
• 把问题简化为：当前位置(i, j)和右边位置(i + 1, j)和下面位置(i, j + 1)之间的问题

base case：

• 当i == row - 1 && j == col - 1时，位于矩阵右下角，即为最终结果

• 当i == row - 1时，位于最后一行，此时只能向右走

• 当j == col - 1时，位于最右一行，此时只能向下走

• 当位于矩阵中间某个位置时(i, j)，此时要判断右边位置(i + 1, j)和下面位置(i, j + 1)中的值谁大谁小

    public static int minPathSum(int matrix[][], int i, int j) {
          // 如果(i,j)就是右下角的元素
          if (i == matrix.length - 1 && j == matrix[0].length - 1) {
            return matrix[i][j];
          }
          // 如果(i,j)在右边界上，只能向下走
          if (j == matrix[0].length - 1) {
            return matrix[i][j] + minPathSum(matrix, i + 1, j);
          }
          // 如果(i,j)在下边界上，只能向右走
          if (i == matrix.length - 1) {
            return matrix[i][j] + minPathSum(matrix, i, j + 1);
          }
                // 不是上述三种情况，那么(i,j)就有向下和向右两种决策，取决策结果最小的那个
          int left = minPathSum(matrix, i, j + 1);
          int down = minPathSum(matrix, i + 1, j);
          return matrix[i][j] + Math.min(left,down );
        }

解法2：动态规划

方法一：

1.生成大小和输入矩阵matrix一样大小的矩阵dp，dp[i][j]表示从左上角（0，0）位置走到（i，j）位置的最小路径；
2.第一行所有位置只能向右走，所以（0，0）位置到（0，j）位置的路径和就是matrix[0][0...j]的值累加，同理，对于第一列的所有位置来说，只能向下走，为matrix[0...i][0]的累加；
3.除第一行和第一列其他位置都有左位置和上位置，选择值最小的位置加上当前值matrix[i][j]就是就是当前路径最小值；

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
   public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = bf.readLine().split(" ");
        int n = Integer.parseInt(strs[0]);
        int m = Integer.parseInt(strs[1]);
        int[][] matrix = new int[n][m];
        for(int i = 0; i < n; i++){
            String[] strs2 = bf.readLine().split(" ");
            for(int j = 0; j < m; j++){
                matrix[i][j] = Integer.parseInt(strs2[j]);
            }
        }
        System.out.print(minPath(matrix));
    }
    public static int minPath(int[][] matrix){
        if(matrix.length==0 || matrix[0].length==0 || matrix==null){
            return 0;
        }
        int rows=matrix.length;
        int cols=matrix[0].length;
        int[][] dp=new int[rows][cols];
        dp[0][0]=matrix[0][0];
        for(int j=1;j<cols;j++){
            dp[0][j]=dp[0][j-1]+matrix[0][j];
        }
        for(int i=1;i<rows;i++){
            dp[i][0]=dp[i-1][0]+matrix[i][0];
        }
        for(int i=1;i<rows;i++){
            for(int j=1;j<cols;j++){
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+matrix[i][j];
            }
        }
        return dp[rows-1][cols-1];
    }
}

方法2：

1.判断行和列哪个比较小，分别记为more和less
2.生成一个长度为less数组arr，用于存储less方向上最小路径和的值
3.沿着more的方向滚动，每次比较左边值和上边值大小并相加

    public static int minPathDp(int[][] m){
        if(m.length==0){
            return 0;
        }
        int more = Math.max(m.length, m[0].length);
        int less = Math.min(m.length, m[0].length);
        int[] arr =new int[less];
        boolean rowmore =more ==m.length;//行数是否大于等于列数；
        arr[0] = m[0][0];
        for (int i = 1; i < less; i++) {
            arr[i] = arr[i-1] +(rowmore?m[0][i]:m[i][0]);
        }
        for (int i = 1; i < more; i++) {
            for (int j = 0; j < arr.length; j++) {
                if(j==0){
                    arr[j] += rowmore?m[i][0]:m[0][i];
                }else{
                    arr[j] = rowmore?m[i][j]+Math.min(arr[j], arr[j-1]):m[j][i]+Math.min(arr[j], arr[j-1]);
                }
            }
        }
        return arr[less-1];  
    }

方法3：空间压缩

import java.util.Arrays; 
public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null) {
            return 0;
        }
        int rowLen = grid.length;
        int colLen = grid[0].length;
        int[] res = new int[colLen + 1];
        Arrays.fill(res, Integer.MAX_VALUE);
        res[1] = 0;
        for (int i = 1; i <= rowLen; i++) {
            for (int j = 1; j <= colLen; j++) {
                //当前点的最小路径和为 : 从左边和上边选择最小的路径和再加上当前点的值
                //res[j]没更新之前就表示i-1行到第j个元素的最小路径和
                //因为是从左往右更新,res[j-1]表示i行第j-1个元素的最小路径和
                res[j] = Math.min(res[j], res[j - 1]) + grid[i - 1][j - 1];
            }
        }
        return res[colLen];
    }
}

总结：

本题压缩空间的方法几乎可以应用到所有需要二维动态规划表的面试题目中，通过一个数组滚动更新的方式节省了大量的空间；未优化前某个位置的动态规划值需要在矩阵中进行两次寻址，优化后只需要一次寻址。。但是在滚动的过程中动态规划表不断的被行数组或者列数组覆盖更新，最后得到的仅仅是动态规划表的最后一行或者最后一列的最小路径和。所以真正的最小路径是不能通过动态规划表回溯得到的。