下降路径最小和【LC931】
给你一个
n x n的 方形 整数数组matrix，请你找出并返回通过matrix的下降路径 的 最小和 。下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置
(row, col)的下一个元素应当是(row + 1, col - 1)、(row + 1, col)或者(row + 1, col + 1)。
- 为了方便边界处理，将dp数组左边增加一列，右边增加一列
class Solution { public int minFallingPathSum(int[][] matrix) { int n = matrix[0].length; if (n == 1) return matrix[0][0]; int[] dp = new int[n + 2]; System.arraycopy(matrix[0], 0, dp, 1, n); dp[0] = dp[n + 1] = Integer.MAX_VALUE; int res = Integer.MAX_VALUE; for (int i = 1; i < n; i++){ int pre = dp[0]; for (int j = 0; j < n; j++){ int tmp = pre; pre = dp[j + 1]; dp[j + 1] = Math.min(tmp, Math.min(dp[j + 1], dp[j + 2])) + matrix[i][j]; } } for (int j = 1; j <= n; j++){ res = Math.min(res, dp[j]); } return res; } }
