流浪小鱼1. 问题背景与核心挑战
三角形最小路径和是动态规划领域的经典问题，题目描述为：给定一个三角形数组，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的节点上。这个问题看似简单，却蕴含着动态规划思想的精髓。
我第一次遇到这个问题是在准备技术面试时，当时被它的多种解法所吸引。最直观的暴力解法时间复杂度高达O(2^n)，而通过动态规划可以优化到O(n^2)。更令人兴奋的是，还能进一步优化空间复杂度到O(n)。这种层层递进的优化过程，正是算法设计的魅力所在。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 基础动态规划解法
2.1 状态定义与转移方程
我们首先定义一个二维dp数组，其中dp[i][j]表示从三角形顶部走到位置(i,j)的最小路径和。状态转移方程可以表示为：
code复制dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
对于每行的第一个元素，只能从上一行的第一个元素下来；对于每行的最后一个元素，只能从上一行的最后一个元素下来。这两种情况需要特殊处理。
2.2 完整实现代码
python复制def minimumTotal(triangle):
n = len(triangle)
dp = [[0]*n for _ in range(n)]
dp[0][0] = triangle[0][0]
for i in range(1, n):
for j in range(i+1):
if j == 0:
dp[i][j] = dp[i-1][j] + triangle[i][j]
elif j == i:
dp[i][j] = dp[i-1][j-1] + triangle[i][j]
else:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
return min(dp[-1])
注意：初始化时dp数组的大小应为n×n，因为最后一行有n个元素。实际使用中可以根据三