Minimum Path Sum
Find the minimum path sum from top-left to bottom-right in a grid.
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Explanation: The optimal path moves along 1 - 2 - 3 - 6, resulting in a minimum accumulated sum of 12.

Question

Minimum Path Sum

Find the minimum path sum from top-left to bottom-right in a grid.

Input: grid = [[1,2,3],[4,5,6]]

Output: 12

Explanation: The optimal path moves along 1 -> 2 -> 3 -> 6, resulting in a minimum accumulated sum of 12.

Anonymous · Accepted Answer

the cleanest way to solve this is with dynamic programming by just overwriting the grid as you iterate through it.

public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            
            // if we are in the top row, we can only come from the left
            if (i == 0) {
                grid[i][j] += grid[i][j - 1];
            } 
            // if we are in the left column, we can only come from above
            else if (j == 0) {
                grid[i][j] += grid[i - 1][j];
            } 
            // otherwise, take the minimum of the cell above or to the left
            else {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
    }
    
    return grid[m - 1][n - 1];
}

Anonymous · Answer

This classical DP problem. Assuming that we are only allowed to move down and
right . We can arrive at a cell in grid G[i][j] from G[i-1][j], G[i][j-1],
G[i-1][j-1]. We need to minimise the sum on the path hence we will move to the
grid G[i][j] carrying minimum value.
G[i][j] = min ( G[i-1][j], G[i][j-1], G[i-1][j-1])
Where base condition G[0][0] = grid[0][0]

pseudocode:
dp[0][0] = grid[i][j]
for i in 0..n{

for j in 0..m{

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) // check for
index out of bound

}

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

Minimum Path Sum

Practice this question with AI

Go Premium

Community Answers

Unlock Full Access

Unlock Full Access

Practice More Questions