问题描述
Given a triangle array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.
Example 1:
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3] ]
Output: 11
Explanation: The triangle looks like: 2 3 4 6 5 7 4 1 8 3 The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
Example 2:
Input: triangle = [[-10] ]
Output: -10
Constraints:
- 1 <= triangle.length <= 200
- triangle[0].length == 1
- triangle[i].length == triangle[i - 1].length + 1
- -10^4 <= triangle[i][j] <= 10^4
Follow up: Could you do this using only O(n) extra space, where n is the total number of rows in the triangle?
问题分析
首先我们考虑最基本的解法：由于上一层的节点只能向下一层的相邻节点移动，即triangle[row][col]要么从triangle[row-1][col]而来，要么从triangle[row-1][col+1]而来；我们便逐层逐个节点按照以上规则更新结果二维数组；这样，我们就得到了达到每个节点的最佳路径和；此时，遍历最后一层，返回最小值即可；
该解法由于需要定义一个和原始triangle相同大小的二维数组，因此空间复杂度为O(N^2)；代码如下：
初始解法
// O(N^2) space
func minimumTotal(triangle [][]int) int {
sum := [][]int{}
for row := 0; row < len(triangle); row++ {
sum = append(sum, make([]int, len(triangle[row])))
}
sum[0][0] = triangle[0][0]
for row := 1; row < len(triangle); row++ {
for col := 0; col < len(triangle[row]); col++ {
if col == 0 {
sum[row][col] = sum[row-1][col] + triangle[row][col]
continue
}
if col == len(triangle[row])-1 {
sum[row][col] = sum[row-1][col-1] + triangle[row][col]
continue
}
sum[row][col] = min(sum[row-1][col-1], sum[row-1][col]) + triangle[row][col]
}
}
lastrow := len(triangle) - 1
ans := sum[lastrow][0]
for i := 1; i < len(sum[lastrow]); i++ {
ans = min(ans, sum[lastrow][i])
}
return ans
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}
优化解法
题目的Follow Up要求仅使用O(N)的空间，我们不妨这样考虑：假设对于triangle[row][col]，从triangle[row+1][col]、triangle[row+1][col+1]到最后一层的最小路径和已知，那么就有 dp[row][col] = min(dp[row+1][col], dp[row+1][col+1]) + triangle[row][col]
但是以上dp方式仍然需要一个二维数组，我们需要将之降为一维。观察以上公式可以发现，上一层的结果总是依赖下一层的相邻节点的计算结果，那么如果我们放弃“行”这个维度，只使用“列”的维度来表示dp，则可以通过滚动更新的方式得到最终的结果；即对于每一层，有dp[col] = min(dp[col], dp[col+1]) + triangle[row][col]；
当我们按照bottom-up的顺序逐层滚动更新后，最终的dp[0]即为所求; 代码如下:
// bottom-up dp, O(N) space
func minimumTotalV2(triangle [][]int) int {
rows := len(triangle)
dp := make([]int, rows)
for i := 0; i < len(triangle); i++ {
dp[i] = triangle[rows-1][i]
}
for row := len(triangle) - 2; row >= 0; row-- {
for col := 0; col <= row; col++ {
dp[col] = min(dp[col], dp[col+1]) + triangle[row][col]
}
}
return dp[0]
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}