문제 설명
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] <= 100
문제풀이
import Foundation
class Solution {
var dp: [Int] = []
var dx = [1,0]
var dy = [0,1]
func minPathSum(_ grid: [[Int]]) -> Int {
let N = grid.count
let M = grid[0].count
dp = Array(repeating: 0, count: N*M)
dp[0] = grid[0][0]
for i in 0..<N {
for j in 0..<M {
for k in 0..<2 {
if i+dy[k] < N && j+dx[k] < M {
let y = i+dy[k]
let x = j+dx[k]
if dp[y*M+x] != 0 {
dp[y*M+x] = min(dp[y*M+x], dp[i*M+j]+grid[y][x])
} else {
dp[y*M+x] = dp[i*M+j]+grid[y][x]
}
}
}
}
}
return dp.last!
}
}