网站icp备案条件,西安网站制作顶,网站服务器买了后怎么做的,教育机构网站建设方案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;}
}
