CLEAN CODE | DYNAMIC PROGRAMMING | RUBY | MINIMUM PATH SUM

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.

leetcode

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


Let me know what you think!
twitter: sprakash24oct
linkedin

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 :)