IOS 算法(中级篇) ----- 最小路径和

今天看到一道算法题, 嗯怎么说呢, 题目特别好理解但是, 没有什么思路无从下手, 给大家分享一下

如果你想知道什么题? 既然你诚心诚意的发问了, 我就大发慈悲的告诉你!

题目: 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

例如:

输入:
[
[1,2,3],
[4,5,6],
[7,8,9]
]
输出: 21
解释: 因为路径 1→2→3→6→9 的总和最小。

输入:
[
[1,0,3],
[4,2,1],
[3,2,2]
]
输出: 6
解释: 因为路径 1→0→2→1→2 的总和最小。

解题思路

这道题题意思很好理解, 但一些实际动手操作的话也是有点难度

因为有几个很难下手点:

每行最小怎么找到?
最小路径怎么选取?
怎么判断处理拐点?
因为题目描述是"一条从左上角到右下角的路径", 所以针对当前单元格(i, j),只用考虑3种情况

左边界单元格只能从上方单元格移来
上边界单元格只能从左边单元格移来
其他情况(i, j) 只能从左边单元格(i-1, j)或上方单元格(i, j-1)移到
接下来我们做的是, 把原来数组值替换, 替换到达这里面的最小值

可以看到
i = 0, j = 0 起点值不变
i ≠ 0, j = 0 左边界, cgrid[i][j] = cgrid[i-1][j] + cgrid[i][j]
i = 0, j ≠ 0 上边界, cgrid[i][j] = cgrid[i][j-1] + cgrid[i][j]
i ≠ 0, j ≠ 0 其余情况, 我们取左边一个单元格, 上面的单元格 两者之中的最小值
即: cgrid[i][j] = cgrid[i-1][j] < cgrid[i][j-1] ?
cgrid[i-1][j] + cgrid[i][j] : cgrid[i][j-1] + cgrid[i][j]

    func minPathSum(_ grid: [[Int]]) -> Int {
        var cgrid = grid
        for i in 0..<cgrid.count {
            for j in 0..<cgrid[0].count {
                if i == 0 && j == 0 {    
                    continue
                }else if i == 0 {
                    cgrid[i][j] = cgrid[i][j-1] + cgrid[i][j]
                }else if j == 0 {
                    cgrid[i][j] = cgrid[i-1][j] + cgrid[i][j]
                }else {
                    cgrid[i][j] = cgrid[i-1][j] < cgrid[i][j-1] ?
                        cgrid[i-1][j] + cgrid[i][j] : cgrid[i][j-1]  + cgrid[i][j]
                }
            }
        }
        return cgrid[cgrid.count - 1][cgrid[0].count - 1]
    }

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)

IOS 算法合集地址