Minimum Path Sum - DP Solution
Another DP problem at LeetCode: https://leetcode.com/problems/minimum-path-sum/
The hints of DP are clear: problem is asking for a min solution, and the brute-force solution is highly exponential, and since the problem does not specify a boundary for the grid, it might be intractable to do it using brute-force.
DP is a construction approach: instead of thinking like recursion where you think in terms of "base case and induction", think more around a "base case and construction", where you'll construct the solution for 0,1,2,....,n-1,n, and then your final solution is whatever you get for n.
Also keep in mind that (usually) DP will require extra space, in our case here O(n)-space.
With that being said, the solution becomes simple: have a "dp" grid which calculates the best solution thus far for the position dp[r,c]. Build that up until dp[n,m], return that value. O(n)-time. Code is below, cheers, Marcelo.
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.
Example:
Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.
The hints of DP are clear: problem is asking for a min solution, and the brute-force solution is highly exponential, and since the problem does not specify a boundary for the grid, it might be intractable to do it using brute-force.
DP is a construction approach: instead of thinking like recursion where you think in terms of "base case and induction", think more around a "base case and construction", where you'll construct the solution for 0,1,2,....,n-1,n, and then your final solution is whatever you get for n.
Also keep in mind that (usually) DP will require extra space, in our case here O(n)-space.
With that being said, the solution becomes simple: have a "dp" grid which calculates the best solution thus far for the position dp[r,c]. Build that up until dp[n,m], return that value. O(n)-time. Code is below, cheers, Marcelo.
public class Solution
{
public int MinPathSum(int[,] grid)
{
if (grid == null) return 0;
int[,] dp = new int[grid.GetLength(0), grid.GetLength(1)];
//Base
dp[0, 0] = grid[0, 0];
for (int r = 1; r < grid.GetLength(0); r++) dp[r, 0] = grid[r, 0] + dp[r - 1, 0];
for (int c = 1; c < grid.GetLength(1); c++) dp[0, c] = grid[0, c] + dp[0, c - 1];
//Construction
for (int r = 1; r < dp.GetLength(0); r++)
for (int c = 1; c < dp.GetLength(1); c++)
dp[r, c] = grid[r, c] + Math.Min(dp[r - 1, c], dp[r, c - 1]);
return dp[dp.GetLength(0) - 1, dp.GetLength(1) - 1];
}
}
Looks good, although it's not necessary to have a 2 dimensional matrix for dp, since we only need 2 rows:
ReplyDeleteclass Solution {
public:
int minPathSum(const vector>& grid) {
if (grid.empty()) return 0;
vector prev(grid[0].size()+1), current(grid[0].size()+1);
for (int i = 0; i < grid[0].size(); ++i) prev[i+1] = prev[i] + grid[0][i];
for (int i = 1; i < grid.size(); ++i) {
current[0] = prev[1];
for (int j = 0; j < grid[i].size(); ++j) {
current[j+1] = grid[i][j] + min(current[j], prev[j+1]);
}
swap(prev, current);
}
return prev.back();
}
};