Day 18 of 30 days Leetcode challenge - Minimum Path Sum

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:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Solution

It's classic Dynamic Programming problem. Result of a point is minimum value of top result with left result.

class Solution {
    func minPathSum(_ grid: [[Int]]) -> Int {
        let n = grid.count
        let m = grid[0].count
        var sums = Array(repeating: Array(repeating:0, count: m), count: n)
        sums[0][0] = grid[0][0]
        
        for i in 1..<n {
            sums[i][0] = grid[i][0] + sums[i - 1][0]
        }
        
        for j in 1..<m {
            sums[0][j] = grid[0][j] + sums[0][j - 1]
        }
        
        for i in 1..<n {
            for j in 1..<m {
                sums[i][j] = grid[i][j] + min(sums[i - 1][j], sums[i][j - 1])
            }
        }
        
        return sums[n - 1][m - 1]
    }
}