鹅厂校招算法题：最小路径和
最小路径和
最近在学习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)
