By: Saurav
2018-03-15 04:12:00 UTC
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 1:
[[1,3,1],
[1,5,1],
[4,2,1]]
Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.
Again, this is a simple dynamic problem if you can visualize it.
In Dynamic programming:
First, we try to guess the solution.
Here the problem is how many ways is it possible to reach a square. A total of 8 ways is our guess.
Out of those 8 ways, we smartly choose only two, as the movement is allowed in only two directions.
Then we take the solutions from solving the two subproblems (ways to reach those square) and combine them according to an aggregation function. In this case, the function is taking a minimum of the total sum values of two subpaths.
For the subproblem of finding the path in the first row and column, we know its one 1.
We then memoize the problem and build next solution based on the previous ones.
It's just like the problem TOTAL NUMBER OF PATHS
Let's see it in action
def min_path_sum(grid)
m = grid.length
n = grid[0].length
return 0 if m < 0 or n < 0
return 1 if n < 1 or m < 1
arr = grid.dup
(1..m-1).each do |i|
arr[i][0] += arr[i-1][0]
end
(1..n-1).each do |i|
arr[0][i] += arr[0][i-1]
end
(1..m-1).each do |i|
(1..n-1).each do |j|
arr[i][j] = [arr[i][j-1], arr[i-1][j]].min + arr[i][j]
end
end
return arr[-1][-1]
end
Owned & Maintained by Saurav Prakash
If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)