【DP】931. 下降路径最小和

本文主要是介绍【DP】931. 下降路径最小和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

法1：标准DP

class Solution {public int minFallingPathSum(int[][] matrix) {if (matrix.length == 0 || matrix[0].length == 0) {return 0;}int m = matrix.length, n = matrix[0].length;int[][] dp = new int[m][n]; // 到达i,j的最小路径和int min = Integer.MAX_VALUE;for (int i = 0; i < n; ++i) { // 首行dp[0][i] = matrix[0][i];if (m == 1) {min = Math.min(min, dp[0][i]);}}for (int i = 1; i < m; ++i) {for (int j = 0; j < n; ++j) {int preMin = dp[i - 1][j];if (j - 1 >= 0) {preMin = Math.min(preMin, dp[i - 1][j - 1]);}if (j + 1 < n) {preMin = Math.min(preMin, dp[i - 1][j + 1]);}dp[i][j] = preMin + matrix[i][j];if (i == m - 1) {min = Math.min(min, dp[i][j]);}}}return min;}
}

这篇关于【DP】931. 下降路径最小和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---