免费创建个人商城网站,网站建设优化服务机构,广州天华建筑设计有限公司,2023新冠结束了吗1289. 下降路径最小和 II 给你一个 n x n 整数矩阵 grid #xff0c;请你返回 非零偏移下降路径 数字和的最小值。
非零偏移下降路径 定义为#xff1a;从 grid 数组中的每一行选择一个数字#xff0c;且按顺序选出来的数字中#xff0c;相邻数字不在原数组的同一列。
示…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;}
}
