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

以下是解决 LeetCode 1289. 下降路径最小和 II 问题的 Java 代码。该问题要求在一个 n × n 的矩阵“grid” 中找到最小下降路径和路径从第一行开始到最后一行结束每次移动到下一行的不同列即不能停留在同一列。方法思路动态规划使用一个一维数组“dp” 来存储到达当前行每列的最小路径和。状态转移对于当前行第“j” 列其最小路径和为当前格子值加上上一行中除同一列外的最小路径和。具体来说先找到上一行所有列中的最小值“min1”和第二小值“min2”。如果上一行第“j” 列的值等于“min1”则当前行第“j” 列的路径和为“grid[i][j] min2”因为不能使用同一列。否则使用“grid[i][j] min1”。初始化第一行的路径和即为各元素本身。结果提取最后一行的路径和最小值即为答案。优化点空间优化仅使用两个一维数组“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; }}代码解释初始化将“dp” 数组初始化为第一行的元素值。逐行处理对于每一行从第二行开始创建一个临时数组“newDp”。遍历上一行的“dp” 数组找出最小值“min1” 和次小值“min2”。对于当前行的每个位置“(i, j)”如果上一行同列的值等于“min1”则当前路径和为“grid[i][j] min2”。否则当前路径和为“grid[i][j] min1”。更新“dp” 为“newDp”继续处理下一行。返回结果处理完所有行后“dp” 数组存储了最后一行各列的路径和返回其中的最小值。此方法高效地解决了问题适用于矩阵大小达到 200×200 的约束条件。