120. 三角形最小路径和

题目描述：

给定一个三角形 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 为三角形的总行数）来解决这个问题吗？

---

解题分析及思路：

此题题解对应动态规划解法：

1. 定义状态： 在这个问题中，状态可以定义为三角形每个位置的最小路径和。为了更方便地表示状态，我们可以直接修改原始三角形数组，将每个位置的值更新为从顶点出发到该位置的最小路径和。

2. 找到状态转移方程： 状态转移方程的推导主要是从底层向上逐步更新每个位置的最小路径和。对于每个位置 (i, j)，可以选择从上一行的 (i-1, j-1) 或 (i-1, j) 移动过来，取两者中的较小值，并加上当前位置的值。 具体的状态转移方程为：triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])

3. 初始化： 由于每个位置的值都会被更新为最小路径和，因此不需要额外的初始化步骤。

4. 递推求解： 使用两层循环，从第二行开始逐行更新每个位置的值，确保通过已知的子问题的解来求解当前问题的解。

5. 计算最终结果： 最终结果即为最后一行中的最小值，因为最后一行中的每个位置都包含了从顶点到该位置的最小路径和。

func minimumTotal(triangle [][]int) int {
	min := func(i, j int) int {
		if i > j {
			return j
		}
		return i
	}
	for index1 := range triangle {
		if index1 == 0 {
			continue
		}
		for index2 := range triangle[index1] {
			if index2 == 0 { // 第一个元素
				triangle[index1][index2] += triangle[index1-1][index2]
			} else if index2 == len(triangle[index1])-1 { // 最后一个元素
				triangle[index1][index2] += triangle[index1-1][index2-1]
			} else {
				triangle[index1][index2] += min(triangle[index1-1][index2-1], triangle[index1-1][index2])
			}
		}
	}
	nums := triangle[len(triangle)-1]
	var number = nums[0]
	for index := range nums {
		number = min(number, nums[index])
	}
	return number
}

优化：

上述需要考虑很多边界问题，所以导致解法也变得更加复杂。

对于自顶向下的最小路径和，同样可以转换为由底部寻找一条路径，到顶点的距离最短。

所以最终的解法：

1. 定义状态： 在这个问题中，状态仍然表示三角形每个位置的最小路径和。同样，我们直接修改原始三角形数组，将每个位置的值更新为从底部到该位置的最小路径和。

2. 找到状态转移方程： 状态转移方程的推导同样是从底层向上逐步更新每个位置的最小路径和。对于每个位置 (i, j)，可以选择从下一行的 (i+1, j) 或 (i+1, j+1) 移动过来，取两者中的较小值，并加上当前位置的值。 具体的状态转移方程为：triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])

3. 初始化： 由于每个位置的值都会被更新为最小路径和，不需要额外的初始化步骤。

4. 递推求解： 使用两层循环，从倒数第二行开始逐行更新每个位置的值，确保通过已知的子问题的解来求解当前问题的解。

5. 计算最终结果： 最终结果即为更新后的三角形顶点的值，因为顶点的值已经包含了从底部到该位置的最小路径和。

func minimumTotal(triangle [][]int) int {
	min := func(i, j int) int {
		if i > j {
			return j
		}
		return i
	}
	for index1 := len(triangle) - 2; index1 >= 0; index1-- {
		for index2 := range triangle[index1] {
			triangle[index1][index2] += min(triangle[index1+1][index2], triangle[index1+1][index2+1])
		}
	}
	return triangle[0][0]
}

复杂度：

• 时间复杂度：复杂度为 O(N^2)，其中 N 为三角形的的行数。
• 空间复杂度：O(1)，原地修改了输入的三角形数组，没有使用额外的空间，因此空间复杂度是常量级别的。

执行结果：

• 执行耗时:4 ms,击败了75.62% 的Go用户
• 内存消耗:2.8 MB,击败了100.00% 的Go用户