人工智能AI面试题-2.6 金字塔最小路径之和

2.6 金字塔最小路径之和 🏔️🚀 题目描述: 给定一个金字塔形状的二维数组，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。例如，给定如下二维数组： ``` [  [2],  [3, 4],  [6, 5, 7],  [4, 1, 8, 3] ] ``` 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。注意：如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。 题目解析: 解法一：二维动态规划 🧮 金字塔为： ``` [2], [3, 4], [6, 5, 7], [4, 1, 8, 3] ``` 反过来直接往上加： ```python dp[i][j] = min(dp[i-1][j], dp[i-1][j+1]) + triangle[i][j] ``` 这个式子的大致意思是，选择上一层的两个相邻节点中和较小的那个，再加上当前节点的值。这是一个经典的动态规划问题。 解法二：一维动态规划 🌟 同样是动态规划，我们可以将问题稍微优化，把每一行的数列都左对齐，如下： ``` [  [2],  [3, 4],  [6, 5, 7],  [4, 1, 8, 3] ] ``` 可以看出来，实际上从上一行到下一行只有两个选择，横坐标不变或加一。我们可以使用一个一维数组 dp[j] 表示从底层到当前层的第 j 个元素所有路径中最小的和。递推关系就是： ```python dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]) ``` 即下一行与它相邻的两个节点中和较小的再加上它自己的值。这样在一维空间内完成了 dp，符合题目挑战。 这个解法的 dp 数组变化如下： ``` [4, 1, 8, 3] [7, 6, 10, 3] ... ``` 参考代码: ```python class Solution(object):   def minimumTotal(self, triangle):     n = len(triangle)     dp = triangle[-1]     for i in range(n - 2, -1, -1):       for j in range(i + 1):         dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])     return dp[0] ``` 这两种动态规划的方法都可以有效地解决问题，选择适合你的方式进行实现。 🌟🔍 希望这些方法能帮助你更专业地解决金字塔最小路径和问题！如果有任何疑问或需要进一步的解释，请随时提出。 💡👨‍💻