最小路径和

最近在学习swift编程语言，接触了swift中数组Array的使用，正好在翻阅之前校招面试鹅厂时的面试算法题。正好可以使用swift中的二维数组来练习下这个题目。

题目

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

说明：每次只能向下或者向右移动一步。

示例:

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

解答

分析

这是一个二维数组求最小路径问题，这里应该类似于早期的RPG游戏，比如仙剑2，金庸群侠传等。其在从地图上的一个点到另外一个点的最小成本就和这里差不多。如下图：

01.png

主角如果想到大绿色点的话，有几种方案可选，计算机肯定是选择一种最优的方案去进行（这里会考虑遮挡）。

那么这个题目该如何做呢？

rows = 1, columns = 1

我们先以数组大小为（columns = 1, rows = 1）的情况来看。

假设array = [2], 那么最小值为2，只有一条路可走。

rows = 2, columns = 2

假设array = [[1, 3], [2, 4 ]]，如下图：

03.png

那么其有两条路可选：

• 1 -> 3 -> 4， 路径和为8

• 1 ->2 -> 4，路径和为7

  那么最小路径就是7，

  在仔细分析下每一步

  首先我们看到达(0, 1)位置最小值为:

  Newf(0, 1) = f(0, 0) + f(0, 1) = 1 + 3 = 4

  到达(1, 0)位置最小值为：

  Newf(1, 0) = f(0, 0) + f(1, 0) = 1 + 2 = 3

  那么到达(1, 1)只有两条路可选了

  • (1, 0) -> (1, 1), Newf(1, 1) = Newf(1, 0) + f(1, 1) = 4 + 4 = 8

  • (0, 1) -> (1, 1), Newf(1, 1) = Newf(0, 1) + f(1, 1) = 3 + 4 = 7

    那么从(0, 0)到达终点(1, 1)的最小路径就是上面两种情况的最小值7。

    如下图所示：

02.png

从上我们可以推导出公式：

• NewF(x, y) = min(NewF(x - 1, y), NewF(x, y - 1)) + F(x, y), (x > 0 && y > 0)

• NewF(x, y) = NewF(x - 1, y) + F(x, y), (x > 0 && y = 0)

• NewF(x, y) = NewF(x, y - 1) + F(x, y), (x = 0 && y > 0)

• NewF(x, y) = F(x, y), (x = 0 && y = 0)

rows = 3, columns = 3

根据前面的公式我们可以直接计算出如果是3 * 3的数组的展示情况如下图：

04.png

代码如下

func minPathSum(_ grid: [[Int]]) -> Int {
    let columns = grid[0].count
    let rows = grid.count
    var mutGrid = grid
    
    for i in 0..<rows {
        for j in 0..<columns {
            var leftValue = Int.max
            var topValue = Int.max
            if i > 0 || j > 0 {
                if i > 0 {
                    topValue = mutGrid[i - 1][j]
                }
                if j > 0 {
                    leftValue = mutGrid[i][j - 1]
                }
                mutGrid[i][j] = min(leftValue, topValue) + mutGrid[i][j]
            }
        }
    }
    
    return mutGrid[rows - 1][columns - 1]
}

复杂度

由于是二维的数组，必须全部遍历，复杂度为O(M * N)