Minimum Path Sum

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:

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

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

Solution:

# @param {Integer[][]} grid
# @return {Integer}
def min_path_sum(grid)
    return if grid.empty? || grid[0].empty?

    m, n = grid.size, grid[0].size

    dp = Array.new(m) { Array.new(n) }

    m.times do |i|
        n.times do |j|
            if i == 0 && j == 0
                dp[i][j] = grid[i][j]
            elsif i == 0
                dp[i][j] = dp[i][j-1] + grid[i][j]
            elsif j == 0
                dp[i][j] = dp[i-1][j] + grid[i][j]
            else
                dp[i][j] = [dp[i][j-1], dp[i-1][j]].min + grid[i][j]
            end
        end
    end

    dp[m-1][n-1]
end