Solution Approach
Solution Overview
There are 3 main approaches to solve this problem:
- Dynamic Programming (2D) - Complex approach
- Dynamic Programming (1D) - Complex approach
- In-place Dynamic Programming - Complex approach
Approach 1: Dynamic Programming (2D)
The key insight for solving this problem is to use dynamic programming to build up the solution from smaller subproblems.
Let's define dp[i][j] as the minimum path sum to reach the cell at position (i, j) from the top-left corner (0, 0).
Since we can only move right or down, to reach the cell (i, j), we must come from either the cell above it (i-1, j) or the cell to its left (i, j-1). Therefore, the recurrence relation is:
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
For the base cases:
dp[0][0] = grid[0][0](the top-left cell)- For the first row (
i = 0),dp[0][j] = grid[0][j] + dp[0][j-1](we can only come from the left) - For the first column (
j = 0),dp[i][0] = grid[i][0] + dp[i-1][0](we can only come from above)
The final answer is dp[m-1][n-1], which represents the minimum path sum to reach the bottom-right corner.
Algorithm:
- Initialize a 2D DP array dp of size m × n, where dp[i][j] represents the minimum path sum to reach the cell at position (i, j).
- Set the base case: dp[0][0] = grid[0][0].
- For the first row (i = 0), set dp[0][j] = grid[0][j] + dp[0][j-1] for all j from 1 to n-1.
- For the first column (j = 0), set dp[i][0] = grid[i][0] + dp[i-1][0] for all i from 1 to m-1.
- For each cell (i, j) where i > 0 and j > 0, calculate dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
- Return dp[m-1][n-1], which represents the minimum path sum to reach the bottom-right corner.
Time Complexity:
We need to fill in the DP table of size m × n, and each cell takes constant time to compute.
Space Complexity:
We use a 2D DP array of size m × n to store the minimum path sum for each cell.
Approach 2: Dynamic Programming (1D)
We can optimize the space complexity of the dynamic programming approach by using a 1D array instead of a 2D array.
The key observation is that when we're calculating dp[i][j], we only need the values from the current row and the row above it. Specifically, we need dp[i-1][j] and dp[i][j-1].
If we use a 1D array dp where dp[j] represents the minimum path sum to reach the cell at position (i, j), then:
- Before the update,
dp[j]represents the minimum path sum to reach the cell at position(i-1, j). - After updating
dp[j-1],dp[j-1]represents the minimum path sum to reach the cell at position(i, j-1).
So, the recurrence relation becomes:
dp[j] = grid[i][j] + min(dp[j], dp[j-1])
We need to be careful with the first column (j = 0), as there is no cell to its left. For the first column, we simply update dp[0] = dp[0] + grid[i][0].
The final answer is dp[n-1], which represents the minimum path sum to reach the bottom-right corner.
Algorithm:
- Initialize a 1D DP array dp of size n, where dp[j] represents the minimum path sum to reach the cell at position (0, j) in the first row.
- Set the base case: dp[0] = grid[0][0].
- For the first row (i = 0), set dp[j] = grid[0][j] + dp[j-1] for all j from 1 to n-1.
- For each row i from 1 to m-1:
- a. Update dp[0] = dp[0] + grid[i][0] (for the first column).
- b. For each column j from 1 to n-1:
- i. Update dp[j] = grid[i][j] + min(dp[j], dp[j-1]).
- Return dp[n-1], which represents the minimum path sum to reach the bottom-right corner.
Time Complexity:
We still need to process each cell in the grid, which takes O(m * n) time.
Space Complexity:
We only use a 1D array of size n to store the minimum path sum for the current row.
Approach 3: In-place Dynamic Programming
We can further optimize the space complexity by modifying the input grid in-place to store the minimum path sum for each cell.
The recurrence relation remains the same:
grid[i][j] = grid[i][j] + min(grid[i-1][j], grid[i][j-1])
We need to be careful with the base cases:
- For the first row (
i = 0),grid[0][j] = grid[0][j] + grid[0][j-1]for all j from 1 to n-1. - For the first column (
j = 0),grid[i][0] = grid[i][0] + grid[i-1][0]for all i from 1 to m-1.
The final answer is grid[m-1][n-1], which represents the minimum path sum to reach the bottom-right corner.
Note that this approach modifies the input grid, which might not be desirable in all situations. If preserving the input is important, we should use one of the previous approaches.
Algorithm:
- For the first row (i = 0), set grid[0][j] = grid[0][j] + grid[0][j-1] for all j from 1 to n-1.
- For the first column (j = 0), set grid[i][0] = grid[i][0] + grid[i-1][0] for all i from 1 to m-1.
- For each cell (i, j) where i > 0 and j > 0, calculate grid[i][j] = grid[i][j] + min(grid[i-1][j], grid[i][j-1]).
- Return grid[m-1][n-1], which represents the minimum path sum to reach the bottom-right corner.
Time Complexity:
We still need to process each cell in the grid, which takes O(m * n) time.
Space Complexity:
We modify the input grid in-place, so we don't need any additional space beyond the input.
Pseudocode
123456789101112131415161718192021222324function minPathSum(grid): m = grid.length n = grid[0].length // Initialize DP array dp = new 2D array of size m × n // Set base case for top-left cell dp[0][0] = grid[0][0] // Set base cases for first row for j from 1 to n-1: dp[0][j] = grid[0][j] + dp[0][j-1] // Set base cases for first column for i from 1 to m-1: dp[i][0] = grid[i][0] + dp[i-1][0] // Fill DP array for i from 1 to m-1: for j from 1 to n-1: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) return dp[m-1][n-1]String Problems
Learning Objective
Understand different approaches to solve the minimum path sum problem and analyze their efficiency.
Solution Approaches
Approach 1: Dynamic Programming (2D)
The key insight for solving this problem is to use dynamic programming to build up the solution from smaller subproblems.
Let's define dp[i][j] as the minimum path sum to reach the cell at position (i, j) from the top-left corner (0, 0).
Since we can only move right or down, to reach the cell (i, j), we must come from either the cell above it (i-1, j) or the cell to its left (i, j-1). Therefore, the recurrence relation is:
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
For the base cases:
dp[0][0] = grid[0][0](the top-left cell)- For the first row (
i = 0),dp[0][j] = grid[0][j] + dp[0][j-1](we can only come from the left) - For the first column (
j = 0),dp[i][0] = grid[i][0] + dp[i-1][0](we can only come from above)
The final answer is dp[m-1][n-1], which represents the minimum path sum to reach the bottom-right corner.
Algorithm:
- Initialize a 2D DP array dp of size m × n, where dp[i][j] represents the minimum path sum to reach the cell at position (i, j).
- Set the base case: dp[0][0] = grid[0][0].
- For the first row (i = 0), set dp[0][j] = grid[0][j] + dp[0][j-1] for all j from 1 to n-1.
- For the first column (j = 0), set dp[i][0] = grid[i][0] + dp[i-1][0] for all i from 1 to m-1.
- For each cell (i, j) where i > 0 and j > 0, calculate dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
- Return dp[m-1][n-1], which represents the minimum path sum to reach the bottom-right corner.
Approach 2: Dynamic Programming (1D)
We can optimize the space complexity of the dynamic programming approach by using a 1D array instead of a 2D array.
The key observation is that when we're calculating dp[i][j], we only need the values from the current row and the row above it. Specifically, we need dp[i-1][j] and dp[i][j-1].
If we use a 1D array dp where dp[j] represents the minimum path sum to reach the cell at position (i, j), then:
- Before the update,
dp[j]represents the minimum path sum to reach the cell at position(i-1, j). - After updating
dp[j-1],dp[j-1]represents the minimum path sum to reach the cell at position(i, j-1).
So, the recurrence relation becomes:
dp[j] = grid[i][j] + min(dp[j], dp[j-1])
We need to be careful with the first column (j = 0), as there is no cell to its left. For the first column, we simply update dp[0] = dp[0] + grid[i][0].
The final answer is dp[n-1], which represents the minimum path sum to reach the bottom-right corner.
Algorithm:
- Initialize a 1D DP array dp of size n, where dp[j] represents the minimum path sum to reach the cell at position (0, j) in the first row.
- Set the base case: dp[0] = grid[0][0].
- For the first row (i = 0), set dp[j] = grid[0][j] + dp[j-1] for all j from 1 to n-1.
- For each row i from 1 to m-1:
- a. Update dp[0] = dp[0] + grid[i][0] (for the first column).
- b. For each column j from 1 to n-1:
- i. Update dp[j] = grid[i][j] + min(dp[j], dp[j-1]).
- Return dp[n-1], which represents the minimum path sum to reach the bottom-right corner.
Approach 3: In-place Dynamic Programming
We can further optimize the space complexity by modifying the input grid in-place to store the minimum path sum for each cell.
The recurrence relation remains the same:
grid[i][j] = grid[i][j] + min(grid[i-1][j], grid[i][j-1])
We need to be careful with the base cases:
- For the first row (
i = 0),grid[0][j] = grid[0][j] + grid[0][j-1]for all j from 1 to n-1. - For the first column (
j = 0),grid[i][0] = grid[i][0] + grid[i-1][0]for all i from 1 to m-1.
The final answer is grid[m-1][n-1], which represents the minimum path sum to reach the bottom-right corner.
Note that this approach modifies the input grid, which might not be desirable in all situations. If preserving the input is important, we should use one of the previous approaches.
Algorithm:
- For the first row (i = 0), set grid[0][j] = grid[0][j] + grid[0][j-1] for all j from 1 to n-1.
- For the first column (j = 0), set grid[i][0] = grid[i][0] + grid[i-1][0] for all i from 1 to m-1.
- For each cell (i, j) where i > 0 and j > 0, calculate grid[i][j] = grid[i][j] + min(grid[i-1][j], grid[i][j-1]).
- Return grid[m-1][n-1], which represents the minimum path sum to reach the bottom-right corner.
Complexity Analysis
Dynamic Programming (2D) Approach
Time Complexity
We need to fill in the DP table of size m × n, and each cell takes constant time to compute.
Space Complexity
We use a 2D DP array of size m × n to store the minimum path sum for each cell.
Dynamic Programming (1D) Approach
Time Complexity
We still need to process each cell in the grid, which takes O(m * n) time.
Space Complexity
We only use a 1D array of size n to store the minimum path sum for the current row.
In-place Dynamic Programming Approach
Time Complexity
We still need to process each cell in the grid, which takes O(m * n) time.
Space Complexity
We modify the input grid in-place, so we don't need any additional space beyond the input.
Pseudocode
Dynamic Programming (2D) Approach
123456789101112131415161718192021222324function minPathSum(grid): m = grid.length n = grid[0].length // Initialize DP array dp = new 2D array of size m × n // Set base case for top-left cell dp[0][0] = grid[0][0] // Set base cases for first row for j from 1 to n-1: dp[0][j] = grid[0][j] + dp[0][j-1] // Set base cases for first column for i from 1 to m-1: dp[i][0] = grid[i][0] + dp[i-1][0] // Fill DP array for i from 1 to m-1: for j from 1 to n-1: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) return dp[m-1][n-1]Dynamic Programming (1D) Approach
12345678910111213141516171819202122function minPathSum(grid): m = grid.length n = grid[0].length // Initialize DP array for first row dp = new 1D array of size n dp[0] = grid[0][0] // Set base cases for first row for j from 1 to n-1: dp[j] = grid[0][j] + dp[j-1] // Fill DP array for i from 1 to m-1: // Update first column dp[0] = dp[0] + grid[i][0] // Update rest of the row for j from 1 to n-1: dp[j] = grid[i][j] + min(dp[j], dp[j-1]) return dp[n-1]In-place Dynamic Programming Approach
123456789101112131415161718function minPathSum(grid): m = grid.length n = grid[0].length // Set base cases for first row for j from 1 to n-1: grid[0][j] = grid[0][j] + grid[0][j-1] // Set base cases for first column for i from 1 to m-1: grid[i][0] = grid[i][0] + grid[i-1][0] // Fill grid for i from 1 to m-1: for j from 1 to n-1: grid[i][j] = grid[i][j] + min(grid[i-1][j], grid[i][j-1]) return grid[m-1][n-1]In-place Dynamic Programming Approach
123456789101112131415161718function minPathSum(grid): m = grid.length n = grid[0].length // Set base cases for first row for j from 1 to n-1: grid[0][j] = grid[0][j] + grid[0][j-1] // Set base cases for first column for i from 1 to m-1: grid[i][0] = grid[i][0] + grid[i-1][0] // Fill grid for i from 1 to m-1: for j from 1 to n-1: grid[i][j] = grid[i][j] + min(grid[i-1][j], grid[i][j-1]) return grid[m-1][n-1]