hello-algo/zh-hant/codes/swift/chapter_dynamic_programming/min_path_sum.swift
Yudong Jin 2a9db6d039
Bug fixes and improvements (#1572)
* Sync zh and zh-hant versions.

* Remove the polyfill.io link from mkdocs.yml

* Update contributors' info for code reviewers and en/zh-hant versions reviewers.

* Fix graph.md

* Update avatars for English version reviewers.

* Sync zh and zh-hant versions.

* Fix two_sum_brute_force.png

* Sync zh and zh-hant versions.
Optimize structrue of index.html.

* Format index.html
2024-11-25 19:21:11 +08:00

123 lines
3.6 KiB
Swift
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

/**
* File: min_path_sum.swift
* Created Time: 2023-07-15
* Author: nuomi1 (nuomi1@qq.com)
*/
/* */
func minPathSumDFS(grid: [[Int]], i: Int, j: Int) -> Int {
//
if i == 0, j == 0 {
return grid[0][0]
}
// +
if i < 0 || j < 0 {
return .max
}
// (i-1, j) (i, j-1)
let up = minPathSumDFS(grid: grid, i: i - 1, j: j)
let left = minPathSumDFS(grid: grid, i: i, j: j - 1)
// (i, j)
return min(left, up) + grid[i][j]
}
/* */
func minPathSumDFSMem(grid: [[Int]], mem: inout [[Int]], i: Int, j: Int) -> Int {
//
if i == 0, j == 0 {
return grid[0][0]
}
// +
if i < 0 || j < 0 {
return .max
}
//
if mem[i][j] != -1 {
return mem[i][j]
}
//
let up = minPathSumDFSMem(grid: grid, mem: &mem, i: i - 1, j: j)
let left = minPathSumDFSMem(grid: grid, mem: &mem, i: i, j: j - 1)
// (i, j)
mem[i][j] = min(left, up) + grid[i][j]
return mem[i][j]
}
/* */
func minPathSumDP(grid: [[Int]]) -> Int {
let n = grid.count
let m = grid[0].count
// dp
var dp = Array(repeating: Array(repeating: 0, count: m), count: n)
dp[0][0] = grid[0][0]
//
for j in 1 ..< m {
dp[0][j] = dp[0][j - 1] + grid[0][j]
}
//
for i in 1 ..< n {
dp[i][0] = dp[i - 1][0] + grid[i][0]
}
//
for i in 1 ..< n {
for j in 1 ..< m {
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
}
}
return dp[n - 1][m - 1]
}
/* */
func minPathSumDPComp(grid: [[Int]]) -> Int {
let n = grid.count
let m = grid[0].count
// dp
var dp = Array(repeating: 0, count: m)
//
dp[0] = grid[0][0]
for j in 1 ..< m {
dp[j] = dp[j - 1] + grid[0][j]
}
//
for i in 1 ..< n {
//
dp[0] = dp[0] + grid[i][0]
//
for j in 1 ..< m {
dp[j] = min(dp[j - 1], dp[j]) + grid[i][j]
}
}
return dp[m - 1]
}
@main
enum MinPathSum {
/* Driver Code */
static func main() {
let grid = [
[1, 3, 1, 5],
[2, 2, 4, 2],
[5, 3, 2, 1],
[4, 3, 5, 2],
]
let n = grid.count
let m = grid[0].count
//
var res = minPathSumDFS(grid: grid, i: n - 1, j: m - 1)
print("從左上角到右下角的最小路徑和為 \(res)")
//
var mem = Array(repeating: Array(repeating: -1, count: m), count: n)
res = minPathSumDFSMem(grid: grid, mem: &mem, i: n - 1, j: m - 1)
print("從左上角到右下角的最小路徑和為 \(res)")
//
res = minPathSumDP(grid: grid)
print("從左上角到右下角的最小路徑和為 \(res)")
//
res = minPathSumDPComp(grid: grid)
print("從左上角到右下角的最小路徑和為 \(res)")
}
}