题目描述
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：
输入：triangle = [[-10]]
输出：-10
题解
思路1: 动态规划
f[i][j] 表示从三角形顶部走到位置(i,j) 的最小路径和
f[i][j] = min(f[i−1][j−1],f[i−1][j])+c[i][j]
static public func minimumTotal1(_ triangle: [[Int]]) -> Int {
let n = triangle.count
if n == 1 {return triangle[0][0]}
var dp = Array(repeating: Array(repeating: Int.max/2, count: n), count: n)
dp[0][0] = triangle[0][0]
for i in 1..<n {
let m = triangle[i].count
for j in 0..<m {
if j>=1 {
dp[i][j] = min(dp[i][j],dp[i-1][j-1] + triangle[i][j])
}
dp[i][j] = min(dp[i][j],dp[i-1][j] + triangle[i][j])
}
}
var ans = Int.max/2
for i in 0..<n {
ans = min(ans,dp[n-1][i])
}
return ans
}
优化
f[i][j] = min(f[i−1][j−1],f[i−1][j])+c[i][j] (0<j<i)
f[i][0] = f[i-1][0] + c[i][0] (j=0)
f[i][i] = f[i-1][i-1] + c[i][i] (j=i)
static public func minimumTotal2(_ triangle: [[Int]]) -> Int {
let n = triangle.count
if n == 1 {return triangle[0][0]}
var dp = Array(repeating: Array(repeating: Int.max/2, count: n), count: n)
dp[0][0] = triangle[0][0]
for i in 1..<n {
dp[i][0] = dp[i-1][0] + triangle[i][0]
for j in 1..<i {
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
}
dp[i][i] = dp[i-1][i-1] + triangle[i][i]
}
var ans = Int.max/2
for i in 0..<n {
ans = min(ans,dp[n-1][i])
}
return ans
}
思路2:动态规划+空间优化
f[i][j] 只与f[i-1][...]有关，与f[i−2][..] 及之前的状态无关。
使用dp0表示上一层节点最小路径和，使用dp1表示当前层节点最小路径和，每次循环后，将dp1恢复原状
static public func minimumTotal3(_ triangle: [[Int]]) -> Int {
let n = triangle.count
if n == 1 {return triangle[0][0]}
var dp0 = Array(repeating: Int.max/2, count: n)
var dp1 = Array(repeating: Int.max/2, count: n)
dp0[0] = triangle[0][0]
for i in 1..<n {
let m = triangle[i].count
for j in 0..<m {
if j>=1 {
dp1[j] = min(dp1[j], dp0[j-1]+triangle[i][j])
}
dp1[j] = min(dp1[j], dp0[j]+triangle[i][j])
}
dp0 = dp1
dp1 = Array(repeating: Int.max/2, count: n)
}
var ans = Int.max/2
for i in 0..<n {
ans = min(ans,dp0[i])
}
return ans
}
优化
f[i][j] 只与f[i-1][...]有关，与f[i−2][..] 及之前的状态无关
我们使用两个长度为n的一维数组进行转移，将i根据奇偶性映射到其中一个一维数组，那么i−1 就映射到了另一个一维数组。这样我们使用这两个一维数组，交替地进行状态转移
static public func minimumTotal4(_ triangle: [[Int]]) -> Int {
let n = triangle.count
if n == 1 {return triangle[0][0]}
var dp = Array(repeating: Array(repeating: Int.max/2, count: n), count: 2)
dp[0][0] = triangle[0][0]
for i in 1..<n {
let curr = i%2
let prew = 1-curr
dp[curr][0] = dp[prew][0] + triangle[i][0]
for j in 1..<i {
dp[curr][j] = min(dp[prew][j], dp[prew][j-1]) + triangle[i][j]
}
dp[curr][i] = dp[prew][i-1] + triangle[i][i]
}
var ans = Int.max/2
for i in 0..<n {
ans = min(ans,dp[(n-1)%2][i])
}
return ans
}
优化
从i到0递减地枚举j，只使用一个长度为n的一维数组f，完成状态转移
为什么只有在递减地枚举j时，才能省去一个一维数组？当我们在计算位置(i,j) 时，f[j+1] 到f[i] 已经是第i 行的值，而f[0] 到f[j] 仍然是第i−1 行的值。
此时我们直接通过f[j]=min(f[j−1],f[j])+c[i][j]进行转移，恰好就是在(i−1,j−1) 和(i−1,j) 中进行选择。
但如果我们递增地枚举j，那么在计算位置(i,j) 时，f[0] 到f[j−1] 已经是第i行的值。如果我们仍然使用上述状态转移方程，那么是在(i,j−1) 和(i−1,j) 中进行选择，就产生了错误
static public func minimumTotal5(_ triangle: [[Int]]) -> Int {
let n = triangle.count
if n == 1 {return triangle[0][0]}
var dp = Array(repeating:Int.max/2, count: n)
dp[0] = triangle[0][0]
for i in 1..<n {
dp[i] = dp[i-1]+triangle[i][i]
for j in (1..<i).reversed() {
dp[j] = min(dp[j],dp[j-1]) + triangle[i][j]
}
dp[0] = dp[0] + triangle[i][0]
}
var ans = Int.max/2
for i in 0..<n {
ans = min(ans,dp[i])
}
return ans
}
参考：https://leetcode-cn.com/problems/triangle
https://leetcode-cn.com/problems/triangle/solution/san-jiao-xing-zui-xiao-lu-jing-he-by-leetcode-solu/
