LeetCode_动态规划_中等_931.下降路径最小和
2023-09-27 14:25:46 时间
1.题目
给你一个 n x n 的方形整数数组 matrix ,请你找出并返回通过 matrix 的下降路径的最小和 。
下降路径可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素)。具体来说,位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
示例 1:
输入:matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出:13
解释:如图所示,为和最小的两条下降路径
示例 2:
输入:matrix = [[-19,57],[-40,-5]]
输出:-59
解释:如图所示,为和最小的下降路径
提示:
n == matrix.length == matrix[i].length
1 <= n <= 100
-100 <= matrix[i][j] <= 100
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-falling-path-sum
2.思路
(1)动态规划
3.代码实现(Java)
//思路1————动态规划
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length;
//res保存下降路径最小和,初始值为Integer.MAX_VALUE
int res = Integer.MAX_VALUE;
//dp[i]:存储每一层对应元素的最小值
int[] dp = new int[n + 2];
//初始化dp
dp[0] = dp[n + 1] = Integer.MAX_VALUE;
for (int j = 1; j <= n; j++) {
dp[j] = matrix[0][j - 1];
}
//处理每一行
for (int i = 1; i < n; i++) {
int temp = 0, last = Integer.MAX_VALUE;
//处理每一列
for (int j = 1; j <= n; j++) {
temp = dp[j];
dp[j] = Math.min(Math.min(last, dp[j]), dp[j + 1]) + matrix[i][j - 1];
last = temp;
}
}
for (int i = 1; i <= n; i++) {
res = Math.min(res, dp[i]);
}
return res;
}
相关文章
- LeetCode高频题62. 不同路径:机器人从左上角到右下角的路径有多少条?纯概率排列组合问题,而不是动态规划题
- JS Leetcode 213. 打家劫舍 II 题解分析,在动态规划基础上感受分治算法的魅力
- LeetCode动态规划基础题-打家劫舍
- 181、【动态规划】leetcode ——72. 编辑距离(C++版本)
- 179、【动态规划】leetcode ——115. 不同的子序列(C++版本)
- 178、【数组/动态规划】leetcode ——392. 判断子序列:双指针+动态规划(C++版本)
- 177、【动态规划】leetcode ——11035. 不相交的线(C++版本)
- 172、【动态规划】leetcode ——714. 买卖股票的最佳时机含手续费 (C++版本)
- 160、【动态规划】leetcode ——279. 完全平方数:二维数组+一维滚动数组(C++版本)
- 157、【动态规划】leetcode ——377. 组合总和 Ⅳ:二维数组+一维滚动数组(C++版本)
- 154、【动态规划】leetcode ——494. 目标和:回溯法+动态规划(C++版本)
- 153、【动态规划】leetcode ——1049. 最后一块石头的重量 II:滚动数组(C++版本)
- 148、【动态规划】leetcode ——63. 不同路径 II:递归法+迭代法(C++版本)
- 动态规划TLE之后转向单调栈的解题路径——LeetCode 84 柱状图中的最大矩形(困难)