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

题目描述
给定一个包含非负整数的 m x n 网格 grid ，每次只能向下或者向右移动一步。请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

解题过程

1. 问题理解与状态定义
   我们需要从网格的左上角 (0, 0) 出发，到达右下角 (m-1, n-1)。每一步的移动方向被严格限制为只能向下或向右。我们的目标是找到所有可能路径中，经过的格子内数字之和最小的那一条路径的和。

   为了解决这个最优化问题，我们采用动态规划。核心思想是：到达某个格子的最小路径和，可以由到达它左边或上边格子的最小路径和推导出来。

   我们定义一个二维数组 dp，其中 dp[i][j] 表示从起点 (0, 0) 走到格子 (i, j) 处的最小路径和。

2. 确定状态转移方程
   我们思考如何计算 dp[i][j]。要走到 (i, j)，上一步只能从两个方向来：

   • 从左边来：即从 (i, j-1) 向右走一步。那么路径和就是 到达 (i, j-1) 的最小路径和 加上 (i, j) 格子本身的值，即 dp[i][j-1] + grid[i][j]。
   • 从上边来：即从 (i-1, j) 向下走一步。那么路径和就是 到达 (i-1, j) 的最小路径和 加上 (i, j) 格子本身的值，即 dp[i-1][j] + grid[i][j]。

   为了得到最小路径和，我们当然要选择这两种来源中成本更小的那个。因此，状态转移方程为：
   dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

3. 初始化边界条件
   状态转移方程依赖于左边和上边的格子。对于最上面一行（i = 0）和最左边一列（j = 0），它们并不完全满足这个依赖关系（没有上边或没有左边），因此我们需要单独初始化。

   • 起点：dp[0][0] 表示从起点到起点的路径和，自然就是 grid[0][0] 本身。
   • 第一行（i = 0, j > 0）：对于第一行的任何格子 (0, j)，由于只能向右走，没有其他选择，所以到达它的路径是唯一的。因此，dp[0][j] = dp[0][j-1] + grid[0][j]。
   • 第一列（j = 0, i > 0）：同理，对于第一列的任何格子 (i, 0)，由于只能向下走，路径也是唯一的。因此，dp[i][0] = dp[i-1][0] + grid[i][0]。

4. 计算顺序与填表
   根据状态转移方程，要计算 dp[i][j]，我们必须先知道它正上方 dp[i-1][j] 和正左方 dp[i][j-1] 的值。因此，一个自然的计算顺序是从左到右，从上到下依次遍历整个网格。这样，当我们计算到某个格子时，它左边和上边的格子的 dp 值都已经被计算出来了。

5. 返回结果
   当我们按照上述顺序遍历并填充满整个 dp 表后，最终的结果就存储在 dp 表的右下角，即 dp[m-1][n-1] 中，它代表了从左上角到右下角的最小路径和。

举例说明
假设网格 grid 为：

[1, 3, 1]
[1, 5, 1]
[4, 2, 1]

我们逐步构建 dp 表：

1. 初始化：

   • dp[0][0] = grid[0][0] = 1
   • 初始化第一行：dp[0][1] = dp[0][0] + grid[0][1] = 1 + 3 = 4； dp[0][2] = dp[0][1] + grid[0][2] = 4 + 1 = 5
   • 初始化第一列：dp[1][0] = dp[0][0] + grid[1][0] = 1 + 1 = 2； dp[2][0] = dp[1][0] + grid[2][0] = 2 + 4 = 6
     此时 dp 表为：

   [1, 4, 5]
   [2, ?, ?]
   [6, ?, ?]
   

2. 填充内部格子：

   • 计算 dp[1][1]：min(dp[0][1], dp[1][0]) + grid[1][1] = min(4, 2) + 5 = 2 + 5 = 7
   • 计算 dp[1][2]：min(dp[0][2], dp[1][1]) + grid[1][2] = min(5, 7) + 1 = 5 + 1 = 6
   • 计算 dp[2][1]：min(dp[1][1], dp[2][0]) + grid[2][1] = min(7, 6) + 2 = 6 + 2 = 8
   • 计算 dp[2][2]：min(dp[1][2], dp[2][1]) + grid[2][2] = min(6, 8) + 1 = 6 + 1 = 7
     填充完毕的 dp 表为：

   [1, 4, 5]
   [2, 7, 6]
   [6, 8, 7]
   

3. 返回结果：dp[2][2] = 7。
   所以，从左上角到右下角的最小路径和为 7。对应的路径是 1 → 1 → 1 → 2 → 1（右，下，右，下，右 或其它等价走法，总和为7）。