64. Minimum Path Sum

Published on March 5, 2023

问题

一个表格m*n，每个都有数字，从左上角走到右下角，如何走路径和最大。

限制是在网格中只能往下或者往右走。

解析

经典网格问题。

初始化可以将左边一列和顶上第一行初始化，因为他们的结果只能来源于他的上一个或者左边一个。

状态转移公式为dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);

代码

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        
        dp[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            dp[0][i] = grid[0][i] + dp[0][i - 1];
        }
        for (int i = 1; i < m; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
}

Minimum Path Sum

Question

A table m*n, each with numbers, goes from the top left corner to the bottom right corner, how to take the path and the maximum.

The restriction is that you can only go down or to the right in the grid.

Solution

Classical grid problem.

The initialization can initialize the left column and the top first row, because their results can only originate from his previous one or the left one.

The state transfer formula is dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);

Code

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        
        dp[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            dp[0][i] = grid[0][i] + dp[0][i - 1];
        }
        for (int i = 1; i < m; i++) {
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
}