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

线性动态规划：最小路径和问题（Minimum Path Sum） 题目描述 给定一个包含非负整数的 m x n 网格 grid ，找出一条从左上角（起点）到右下角（终点）的路径，使得路径上的数字总和最小。每次只能向右或向下移动一步。 示例 输入： 输出： 7 解释：路径 1 → 3 → 1 → 1 → 1 的总和最小，为 7。 解题过程 1. 定义状态 设 dp[i][j] 表示从起点 (0, 0) 到达位置 (i, j) 的最小路径和。目标是求 dp[m-1][n-1] 。 2. 状态转移方程 对于起点 (0, 0) ：路径和就是网格中的值，即 dp[0][0] = grid[0][0] 。 对于第一行（ i = 0, j > 0 ）：只能从左边向右移动到达，因此： dp[0][j] = dp[0][j-1] + grid[0][j] 。 对于第一列（ j = 0, i > 0 ）：只能从上方向下移动到达，因此： dp[i][0] = dp[i-1][0] + grid[i][0] 。 对于其他位置（ i > 0, j > 0 ）：可以从上方或左方到达，选择路径和较小的方向： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] 。 3. 初始化 直接按照上述规则初始化 dp 数组的起点、第一行和第一列。 4. 计算顺序 按行从上到下、每行从左到右计算 dp[i][j] ，确保在计算 dp[i][j] 时， dp[i-1][j] 和 dp[i][j-1] 已计算。 5. 示例推导 对示例网格进行逐步计算： dp[0][0] = 1 第一行： dp[0][1] = 1 + 3 = 4 , dp[0][2] = 4 + 1 = 5 第一列： dp[1][0] = 1 + 1 = 2 , dp[2][0] = 2 + 4 = 6 dp[1][1] = min(dp[0][1]=4, dp[1][0]=2) + 5 = 2 + 5 = 7 dp[1][2] = min(5, 7) + 1 = 5 + 1 = 6 dp[2][1] = min(6, 7) + 2 = 6 + 2 = 8 dp[2][2] = min(8, 6) + 1 = 6 + 1 = 7 最终结果为 dp[2][2] = 7 。 6. 优化（可选） 可复用原网格或使用一维数组降低空间复杂度，但需保留前一行的数据以支持状态转移。 7. 复杂度分析 时间复杂度：O(m × n)，需遍历整个网格。 空间复杂度：O(m × n)（直接使用二维数组）或 O(n)（优化为一维数组）。 通过以上步骤，即可高效求解最小路径和问题。