Description:
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Examples:
Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Example 2:
Input: grid = [[1,2,3],[4,5,6]]
Output: 12Solution in Python:
To solve the problem of finding a path from the top-left corner to the bottom-right corner of a grid that minimizes the sum of all numbers along its path, we will use a dynamic programming approach.
Steps to Solve the Problem:
- Define the Problem in Terms of Subproblems:
- We need to calculate the minimum path sum to reach each cell
(i, j)starting from the top-left corner(0, 0). - The minimum path sum to reach cell
(i, j)can be derived from the minimum path sum to reach either cell(i-1, j)(the cell above) or cell(i, j-1)(the cell to the left).
- We need to calculate the minimum path sum to reach each cell
- Initialize the Base Cases:
- The minimum path sum to reach the starting cell
(0, 0)is the value of the cell itself. - For the first row and the first column, the minimum path sum is the cumulative sum of the cells along that row or column.
- The minimum path sum to reach the starting cell
- Create and Populate the DP Table:
- Create a 2D array
dpwheredp[i][j]represents the minimum path sum to reach cell(i, j). - Iterate through the grid, and for each cell
(i, j), updatedp[i][j]based on the values from the cell above it and the cell to the left of it.
- Create a 2D array
- Return the Result:
- The value at
dp[m-1][n-1]will give us the minimum path sum to the bottom-right corner of the grid.
- The value at
Python
from typing import List
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
# Get the dimensions of the grid
m, n = len(grid), len(grid[0])
# Create a 2D dp array initialized to 0
dp = [[0] * n for _ in range(m)]
# Initialize the starting point
dp[0][0] = grid[0][0]
# Fill the first row
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
# Fill the first column
for i in range(1, m):
dp[i][0] = dp[i-1][0] + grid[i][0]
# Fill the dp table
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
# Return the minimum path sum to reach the bottom-right corner
return dp[m-1][n-1]Detailed Explanation:
- Initialization:
m, n = len(grid), len(grid[0])gets the dimensions of the grid.dp = [[0] * n for _ in range(m)]creates anm x ngrid initialized to0.
- Setting Up the Starting Point:
dp[0][0] = grid[0][0]initializes the starting point with the value of the top-left cell.
- Filling the First Row and Column:
- The loop
for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j]fills the first row by accumulating the values of the cells from the left. - The loop
for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0]fills the first column by accumulating the values of the cells from above.
- The loop
- Filling the DP Table:
- The nested loop
for i in range(1, m): for j in range(1, n): dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]computes the minimum path sum to each cell(i, j)by taking the minimum of the sums from the cell above and the cell to the left and adding the value of the current cell.
- The nested loop
- Result:
return dp[m-1][n-1]returns the value at the bottom-right corner of the grid, which represents the minimum path sum to that cell.
This approach ensures that we efficiently compute the minimum path sum using dynamic programming in O(m * n) time complexity, which is suitable given the problem constraints.
Solution in Javascript:
JavaScript
/**
* @param {number[][]} grid
* @return {number}
*/
var minPathSum = function(grid) {
// Get the dimensions of the grid
const m = grid.length;
const n = grid[0].length;
// Create a 2D dp array initialized to 0
const dp = Array.from({ length: m }, () => Array(n).fill(0));
// Initialize the starting point
dp[0][0] = grid[0][0];
// Fill the first row
for (let j = 1; j < n; j++) {
dp[0][j] = dp[0][j-1] + grid[0][j];
}
// Fill the first column
for (let i = 1; i < m; i++) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
// Fill the dp table
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
// Return the minimum path sum to reach the bottom-right corner
return dp[m-1][n-1];
};Solution in Java:
Java
class Solution {
public int minPathSum(int[][] grid) {
// Get the dimensions of the grid
int m = grid.length;
int n = grid[0].length;
// Create a 2D dp array initialized to 0
int[][] dp = new int[m][n];
// Initialize the starting point
dp[0][0] = grid[0][0];
// Fill the first row
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// Fill the first column
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
// Fill the dp table
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
// Return the minimum path sum to reach the bottom-right corner
return dp[m - 1][n - 1];
}
}Solution in C#:
C#
public class Solution {
public int MinPathSum(int[][] grid) {
// Get the dimensions of the grid
int m = grid.Length;
int n = grid[0].Length;
// Create a 2D dp array initialized to 0
int[,] dp = new int[m, n];
// Initialize the starting point
dp[0, 0] = grid[0][0];
// Fill the first row
for (int j = 1; j < n; j++) {
dp[0, j] = dp[0, j - 1] + grid[0][j];
}
// Fill the first column
for (int i = 1; i < m; i++) {
dp[i, 0] = dp[i - 1, 0] + grid[i][0];
}
// Fill the dp table
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i, j] = Math.Min(dp[i - 1, j], dp[i, j - 1]) + grid[i][j];
}
}
// Return the minimum path sum to reach the bottom-right corner
return dp[m - 1, n - 1];
}
}