LeetCode_02_1289. 下降路径最小和 II

1289. 下降路径最小和 II

---

给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。

非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。

示例1

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
输出：13
解释：
所有非零偏移下降路径包括：
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。

示例2

输入：grid = [[7]]
输出：7

代码实现

class Solution {public int minFallingPathSum(int[][] grid) {int n = grid.length;int[][] dp = new int[n][n];// 初始化第一行for (int j = 0; j < n; j++) {dp[0][j] = grid[0][j];}// 计算dp数组的值for (int i = 1; i < n; i++) {for (int j = 0; j < n; j++) {int minVal = Integer.MAX_VALUE;for (int x = 0; x < n; x++) {if (x != j) {minVal = Math.min(minVal, dp[i - 1][x]);}}dp[i][j] = minVal + grid[i][j];}}// 找到最后一行的最小值int minSum = Integer.MAX_VALUE;for (int j = 0; j < n; j++) {minSum = Math.min(minSum, dp[n - 1][j]);}return minSum;}
}