下降路径最小和 II【LC1289】
给你一个
n x n整数矩阵grid，请你返回 非零偏移下降路径 数字和的最小值。非零偏移下降路径 定义为：从
grid数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
- 优化：记录上一行最小值和次小值的列下标，本行的每个位置一定是从上一行的最小值或者次小值转移得到的，如果最小值的列下标和本行相同，那么选择次小值；否则选择最小值。
- 实现
class Solution { public int minFallingPathSum(int[][] grid) { int n = grid.length, m = grid[0].length; // 记录上一行最小值和次小值的列下标 // 本行的每个位置一定是从上一行的最小值或者次小值转移得到的，如果最小值的列下标和本行相同，那么选择次小值；否则选择最小值 int first = -1, second = -1; for (int i = 0; i < n; i++){ int min1 = -1, min2 = -1; for (int j = 0; j < m; j++){ if (first != -1 && first != j){ grid[i][j] += grid[i - 1][first]; }else if(second != -1){ grid[i][j] += grid[i - 1][second]; } if (min1 == -1 || grid[i][j] < grid[i][min1]){ min2 = min1; min1 = j; }else if(min2 == -1 || grid[i][j] < grid[i][min2]){ min2 = j; } } first = min1; second = min2; } int res = Integer.MAX_VALUE; for (int j = 0; j < m; j++){ res = Math.min(grid[n - 1][j], res); } return res; } }
