题目描述
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下一行中与这个结点正下方或者正下方右边的结点。
方法一：动态规划（自底向上）
解题步骤：
- 从三角形的最后一行开始，用一个数组
dp存储到当前行每个元素的最小路径和。 - 对于三角形的每一行，更新
dp数组中的每个值，使其等于当前元素加上它下面行中相邻元素的较小者。 - 最终，
dp数组的第一个元素将包含从顶部到底部的最小路径和。
Python 代码示例
def minimumTotal(triangle):
dp = triangle[-1]
for i in range(len(triangle) - 2, -1, -1):
for j in range(len(triangle[i])):
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
return dp[0]
方法一使用动态规划的自底向上方式来计算三角形的最小路径和。我们将通过 ASCII 图形来展示这个方法的工作过程，特别是如何迭代更新从底层到顶层的计算过程。
算法图解
考虑一个具体的三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
我们从三角形的最后一行开始，并逐行向上更新每个元素的最小路径和。
初始状态
- 初始化
dp数组为三角形的最后一行：
dp: [4, 1, 8, 3]
更新到第二行
- 更新
dp数组为倒数第二行的每个元素加上其下面行中相邻元素的较小者：
更新过程：
dp[0]: 6 + min(4, 1) = 6 + 1 = 7
dp[1]: 5 + min(1, 8) = 5 + 1 = 6
dp[2]: 7 + min(8, 3) = 7 + 3 = 10
dp: [7, 6, 10]
更新到第三行
- 同理，更新
dp数组为第三行的每个元素加上其下面行中相邻元素的较小者：
更新过程：
dp[0]: 3 + min(7, 6) = 3 + 6 = 9
dp[1]: 4 + min(6, 10) = 4 + 6 = 10
dp: [9, 10]
更新到第四行（顶行）
- 最后更新顶行：
更新过程：
dp[0]: 2 + min(9, 10) = 2 + 9 = 11
dp: [11]
结果
- 自底向上的动态规划计算结束后，
dp数组的第一个元素11就是从顶部到底部的最小路径和。
总结步骤
- 初始化
dp数组为三角形的最后一行。 - 从三角形的倒数第二行开始，向上逐行更新
dp数组，每个元素都更新为自己加上下一行相邻两个元素中较小的一个。 - 这个过程一直重复到三角形的顶部。
dp[0]存储了最终的最小路径和。
方法二：递归 + 记忆化
解题步骤：
- 创建一个与三角形同样大小的
memo数组，用于存储到每个元素的最小路径和，避免重复计算。 - 使用递归函数，从顶部开始计算每个元素到底部可能的最小路径和，将结果存储在
memo中。 - 返回顶部元素的最小路径和。
Python 代码示例
def minimumTotal(triangle):
memo = [[None] * len(row) for row in triangle]
def helper(row, col):
if row == len(triangle):
return 0
if memo[row][col] is None:
memo[row][col] = triangle[row][col] + min(helper(row + 1, col), helper(row + 1, col + 1))
return memo[row][col]
return helper(0, 0)
方法三：动态规划（自顶向下）
解题步骤：
- 使用一个
dp数组，初始化为三角形的第一行。 - 逐行更新
dp数组，使每个元素代表从顶部到当前元素的最小路径和。 - 在遍历的过程中，注意边界元素的处理，因为它们只有一种选择。
- 最后一行中的最小值即为所求的最小路径和。
Python 代码示例
def minimumTotal(triangle):
dp = triangle[0]
for i in range(1, len(triangle)):
prev = dp[:]
for j in range(len(triangle[i])):
if j == 0:
dp[j] = prev[j] + triangle[i][j]
elif j == len(triangle[i]) - 1:
dp[j] = prev[j - 1] + triangle[i][j]
else:
dp[j] = min(prev[j - 1], prev[j]) + triangle[i][j]
return min(dp)
算法分析
- 时间复杂度：
- 方法一和三：(O(n^2))，其中 (n) 是三角形的行数。
- 方法二：理论上也是 (O(n^2))，但由于递归调用栈的开销，可能会慢一些。
- 空间复杂度：
- 方法一和三：(O(n))，仅使用了一维数组进行存储。
- 方法二：(O(n^2))，使用了一个全尺寸的备忘录数组加上递归栈。
不同算法的优劣势对比
- 动态规划（自底向上）（方法一）非常直观和高效，通常是解决此类问题的首选方法。
- 递归 + 记忆化（方法二）易于理解和实现，但空间消耗较大。
- 动态规划（自顶向下）（方法三）保持了问题的自然顺序，易于理解，但在边界处理上稍微复杂一些。
应用示例
这种类型的最小路径问题在图形路径计算、资源优化分配及其他需要最优决策的领域有广泛的应用。