元宝Hunyuan LeetCode 1289.下降路径最小和 || public int minFallingPathSum(int[][] grid)

以下是解决 LeetCode 1289. 下降路径最小和 II 问题的 Java 代码。该问题要求在一个 n × n 的矩阵
“grid” 中找到最小下降路径和，路径从第一行开始，到最后一行结束，每次移动到下一行的不同列（即不能停留在同一列）。

方法思路

1. 动态规划：使用一个一维数组
   “dp” 来存储到达当前行每列的最小路径和。
2. 状态转移：对于当前行第
   “j” 列，其最小路径和为当前格子值加上上一行中除同一列外的最小路径和。具体来说：
   • 先找到上一行所有列中的最小值（
     “min1”）和第二小值（
     “min2”）。
   • 如果上一行第
     “j” 列的值等于
     “min1”，则当前行第
     “j” 列的路径和为
     “grid[i][j] + min2”（因为不能使用同一列）。
   • 否则，使用
     “grid[i][j] + min1”。
3. 初始化：第一行的路径和即为各元素本身。
4. 结果提取：最后一行的路径和最小值即为答案。

优化点

• 空间优化：仅使用两个一维数组（
  “dp” 和
  “newDp”）交替存储当前行和上一行的状态，避免使用二维数组。
• 时间优化：每行处理中，通过一次遍历找到上一行的最小值和次小值，使得每个单元格的状态转移时间为 O(1)，总时间复杂度为 O(n²)。

代码实现

class Solution {
public int minFallingPathSum(int[][] grid) {
int n = grid.length;
if (n == 0) return 0;

int[] dp = new int[n]; // 初始化第一行 for (int j = 0; j < n; j++) { dp[j] = grid[0][j]; } // 从第二行开始处理 for (int i = 1; i < n; i++) { int[] newDp = new int[n]; int min1 = Integer.MAX_VALUE; // 最小值 int min2 = Integer.MAX_VALUE; // 次小值 // 找出上一行的最小值和次小值 for (int k = 0; k < n; k++) { if (dp[k] < min1) { min2 = min1; min1 = dp[k]; } else if (dp[k] < min2) { min2 = dp[k]; } } // 更新当前行的状态 for (int j = 0; j < n; j++) { if (dp[j] == min1) { newDp[j] = grid[i][j] + min2; } else { newDp[j] = grid[i][j] + min1; } } dp = newDp; // 更新上一行为当前行 } // 找出最后一行的最小值 int ans = dp[0]; for (int j = 1; j < n; j++) { if (dp[j] < ans) { ans = dp[j]; } } return ans; }

}

代码解释

1. 初始化：将
   “dp” 数组初始化为第一行的元素值。
2. 逐行处理：
   • 对于每一行（从第二行开始），创建一个临时数组
     “newDp”。
   • 遍历上一行的
     “dp” 数组，找出最小值
     “min1” 和次小值
     “min2”。
   • 对于当前行的每个位置
     “(i, j)”：
     • 如果上一行同列的值等于
       “min1”，则当前路径和为
       “grid[i][j] + min2”。
     • 否则，当前路径和为
       “grid[i][j] + min1”。
   • 更新
     “dp” 为
     “newDp”，继续处理下一行。
3. 返回结果：处理完所有行后，
   “dp” 数组存储了最后一行各列的路径和，返回其中的最小值。

此方法高效地解决了问题，适用于矩阵大小达到 200×200 的约束条件。