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

package com.hhdd.dp;

/**
 * 给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。
 * <p>
 * 题目链接：https://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb?tpId=295&tqId=1009012&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3Ftab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295
 *
 * @Author HuangLusong
 * @Date 2022/4/2 21:08
 */
public class 矩阵的最小路径和 {

    /**
     * 先通过递归，暴力解决下
     *
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum(int[][] matrix) {
        // write code here
        return dp(matrix);

    }

    /**
     * 递归方式获取从当前位置到右下角的路径的最小值
     *
     * @param matrix
     * @param curRow
     * @param curCol
     * @return
     */
    public int recursion(int[][] matrix, int curRow, int curCol) {
        /**
         * 如果当前位置是最右下角，直接返回当前位置的值就好
         */
        if (curRow == matrix.length - 1 && curCol == matrix[0].length - 1) {
            return matrix[curRow][curCol];
        }
        /**
         * 暂存向右走的值
         */
        int tempRight = Integer.MAX_VALUE;
        /**
         * 暂存向下走的值
         */
        int tempDown = Integer.MAX_VALUE;
        if (curCol + 1 < matrix[0].length) {
            // 向右走
            tempRight = matrix[curRow][curCol] + recursion(matrix, curRow, curCol + 1);
        }
        if (curRow + 1 < matrix.length) {
            // 向下走
            tempDown = matrix[curRow][curCol] + recursion(matrix, curRow + 1, curCol);
        }
        // 选出最小的返回
        return Math.min(tempDown, tempRight);
    }

    /**
     * 通过dp的方式解决
     * 又是找规律
     * dp[i][j]表示从i,j到最右下角的最小距离，先把边界解决了，规律就显而易见了
     *
     * @param matrix
     * @return
     */
    public int dp(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        int[][] dp = new int[rows][cols];

        // 最右下角必然是本身
        dp[rows - 1][cols - 1] = matrix[rows - 1][cols - 1];
        //最下面那行必然直接加就好
        for (int i = cols - 2; i >= 0; i--) {
            dp[rows - 1][i] = matrix[rows - 1][i] + dp[rows - 1][i + 1];
        }
        //最右边那列必然也是直接加
        for (int i = rows - 2; i >= 0; i--) {
            dp[i][cols - 1] = matrix[i][cols - 1] + dp[i + 1][cols - 1];
        }
        //下面直接做缩圈的操作就好
        for (int i = rows - 2; i >= 0; i--) {
            for (int j = cols - 2; j >= 0; j--) {
                // 依赖于右边和下边的值，取小的那个
                dp[i][j] = matrix[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
            }
        }

        return dp[0][0];
    }


    public static void main(String[] args) {
        矩阵的最小路径和 demo = new 矩阵的最小路径和();
        int[][] matrix = new int[][]{
//                {1,2}
                {1, 3, 5, 9},
                {8, 1, 3, 4},
                {5, 0, 6, 1},
                {8, 8, 4, 0}
        };
        System.out.println("demo.minPathSum(matrix) = " + demo.minPathSum(matrix));
    }
}