120. 三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
示例：
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
分析：
连续两周的题可能都是动态规划，今天这道感觉比较简单，转移方程很好找，顶点到(i, j)位置的路径和状态仅由(i - 1, j)与(i - 1, j - 1)位置决定。
代码（Golang）：
// 一、动态规划，n^2空间复杂度
func minimumTotal(triangle [][]int) int {
n := len(triangle)
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, i + 1)
}
dp[0][0] = triangle[0][0]
for i := 1; i < n; i++ {
for j := 0; j < i + 1; j++ {
if j == 0 {
dp[i][j] = dp[i - 1][j] + triangle[i][j]
} else if j == i {
dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]
} else {
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j]
}
}
}
return min(dp[n - 1]...)
}
// 二、滚动数组优化，只保留两层的结果
func minimumTotal1(triangle [][]int) int {
n := len(triangle)
dp := make([][]int, 2)
for i := 0; i < 2; i++ {
dp[i] = make([]int, n)
}
dp[0][0] = triangle[0][0]
for i := 1; i < n; i++ {
curr := i % 2
prev := 1 - curr
dp[curr][0] = dp[prev][0] + triangle[i][0]
for j := 1; j < i + 1; j++ {
dp[curr][j] = min(dp[prev][j - 1], dp[prev][j]) + triangle[i][j]
}
dp[curr][i] = dp[prev][i - 1] + triangle[i][i]
}
ans := math.MaxInt32
for i := 0; i < n; i++ {
ans = min(ans, dp[(n - 1) % 2][i])
}
return ans
}
小结：
这两周一直再写动态规划的题目，由一开始只能看出题目可以用动态规划求解，到自己能找出转移方程，已经进步了很多。只是滚动数组、压缩状态的技巧掌握的还不是很熟练。