线性动态规划：最小下降路径和

题目描述
给定一个大小为 n x n 的整数矩阵 matrix，找出一条从顶部到底部的路径，使得路径上的数字之和最小。路径的移动规则为：从第一行的任意元素出发，每次可以移动到下一行相邻的元素（即正下方、左下方或右下方）。要求返回最小的路径和。

例如：
输入：
matrix = [
[2, 1, 3],
[6, 5, 4],
[7, 8, 9]
]
输出：13
解释：最小路径为 1 → 5 → 7，和为 1 + 5 + 7 = 13。

解题过程

1. 问题分析

• 路径从第一行开始，在最后一行结束，移动方向受相邻限制。
• 目标：最小化路径和，需考虑所有可能的路径。
• 关键观察：到达第 i 行第 j 列的最小路径和，取决于上一行能到达当前位置的三个相邻位置（左上、正上、右上）的最小值。

2. 定义状态
设 dp[i][j] 表示从第一行出发，到达第 i 行第 j 列的最小路径和。

3. 状态转移方程
对于第 i 行第 j 列：

• 若 j = 0（最左列），只能从正上方 (i-1, j) 或右上方 (i-1, j+1) 转移。
• 若 j = n-1（最右列），只能从正上方 (i-1, j) 或左上方 (i-1, j-1) 转移。
• 其他情况，可从左上方 (i-1, j-1)、正上方 (i-1, j)、右上方 (i-1, j+1) 转移。

转移方程：

dp[i][j] = matrix[i][j] + min(
    dp[i-1][j-1] if j > 0 else float('inf'),
    dp[i-1][j],
    dp[i-1][j+1] if j < n-1 else float('inf')
)

4. 初始化
第一行的路径和就是矩阵第一行的值：
dp[0][j] = matrix[0][j]

5. 计算顺序与边界处理

• 按行从上到下计算（i 从 1 到 n-1）。
• 每行内从左到右遍历列（j 从 0 到 n-1）。
• 注意边界列的特殊处理（避免索引越界）。

6. 答案提取
最小路径和出现在最后一行：
min(dp[n-1][j])，其中 j 遍历最后一行的所有列。

7. 示例演算
以输入矩阵为例：

matrix = [
  [2, 1, 3],
  [6, 5, 4],
  [7, 8, 9]
]

初始化：
dp[0] = [2, 1, 3]

计算第二行（i=1）：

• j=0：来自上方(0,0)或右上方(0,1)，min(2,1)=1 → dp[1][0] = 6 + 1 = 7
• j=1：来自左(0,0)、上(0,1)、右(0,2)，min(2,1,3)=1 → dp[1][1] = 5 + 1 = 6
• j=2：来自上(0,1)或左(0,2)，min(1,3)=1 → dp[1][2] = 4 + 1 = 5
  dp[1] = [7, 6, 5]

计算第三行（i=2）：

• j=0：来自上(1,0)或右(1,1)，min(7,6)=6 → dp[2][0] = 7 + 6 = 13
• j=1：来自左(1,0)、上(1,1)、右(1,2)，min(7,6,5)=5 → dp[2][1] = 8 + 5 = 13
• j=2：来自左(1,1)或上(1,2)，min(6,5)=5 → dp[2][2] = 9 + 5 = 14
  dp[2] = [13, 13, 14]

最终答案：min(13, 13, 14) = 13

8. 复杂度分析

• 时间复杂度：O(n²)，遍历矩阵每个元素一次。
• 空间复杂度：O(n²)，可优化至 O(n)（仅保存上一行 dp 值）。