刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/triangle/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定一个三角形 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 <= triangle.length <= 200
• triangle[0].length == 1
• triangle[i].length == triangle[i - 1].length + 1
• -10^4 <= triangle[i][j] <= 10^4

进阶：
你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

思路

动态规划

动态规划思路应该还是很简单的

• dp[i][j] 为 (i, j) 坐标位置的最小路径和
• 初始化 triangle[][]
• 转移方程为 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j])

然后看到这个转移方程，其实可以很简单的看出来 滚动数组 的味道，用来优化 dp 数组
当然，如果从前往后遍历的话，dp[i] 位置影响的其实是 (i+1, j) 和 (i+1, j+1)，会影响到 dp[i+1]，但是如果 从后往前遍历，则不会有这个顾虑，所以我们可以改为从后往前遍历，避免影响

自底向上

当时优化完动规数组时，突然就意识到，其实纵向上的影响也是如此，如果自底向上层层计算，其实根本就不需要动规就可以了，只是这样一来，我们就改变了原数组的内容，如果题目有限制就不能使用此方法了

思路大体就是这些，具体看代码，细节在注释了～

代码

动态规划

func minimumTotal(triangle [][]int) int {
	n := len(triangle)
	// 初始化
	dp := make([]int, n)
	dp[0] = triangle[0][0]

	// 状态转移方程 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j])
	// 空间优化后，状态转移方程变为：
	// 1、 每行最后一个值，dp[i] = dp[i-1] + triangle[i][i])
	// 2、 每行第一个值，dp[0] = dp[0] + triangle[i][0])
	// 3、 每行中间值，dp[j] = min(dp[j], dp[j-1]) + triangle[i][j]) -- i 为当前处理行数
	res := dp[0]
	for i := 1; i <= n-1; i++ {
		// 每行最后一个值
		dp[i] = dp[i-1] + triangle[i][i]
		// 最后一趟处理中兼顾比较得到结果
		if i == n-1 {
			res = dp[i]
		}
		// j = len(triangle[i]) - 2, 转化一下就是 i-1
		for j := i - 1; j >= 0; j-- {
			// 每行第一个值
			if j == 0 {
				dp[j] = dp[j] + triangle[i][j]
			} else {
				// 每行中间值
				dp[j] = min(dp[j], dp[j-1]) + triangle[i][j]
			}
			// 最后一趟处理中兼顾比较得到结果
			if i == n-1 && dp[j] < res {
				res = dp[j]
			}
		}
	}
	return res
}

自下而上

func minimumTotal(triangle [][]int) int {
	// 自底向上遍历
	for i :=len(triangle) -2; i>=0; i-- {
		for j := len(triangle[i]) -1; j >=0; j-- {
			triangle[i][j] = min(triangle[i+1][j], triangle[i+1][j+1]) + triangle[i][j]
		}
	}
	return triangle[0][0]
}