对于学校网站建设的建议,免费的app开发工具,wordpress the7不显示分类页,做推送的网站推荐2023-08-10每日一题
一、题目编号
1289. 下降路径最小和 II二、题目链接
点击跳转到题目位置
三、题目描述
给你一个 n x n 整数矩阵 grid #xff0c;请你返回 非零偏移下降路径 数字和的最小值。
非零偏移下降路径 定义为#xff1a;从 grid 数组中的每一行选择一个数…2023-08-10每日一题
一、题目编号
1289. 下降路径最小和 II二、题目链接
点击跳转到题目位置
三、题目描述
给你一个 n x n 整数矩阵 grid 请你返回 非零偏移下降路径 数字和的最小值。
非零偏移下降路径 定义为从 grid 数组中的每一行选择一个数字且按顺序选出来的数字中相邻数字不在原数组的同一列。
示例 1
示例 2 提示
n grid.length grid[i].length1 n 200-99 grid[i][j] 99
四、解题代码
class Solution {
public:int minFallingPathSum(vectorvectorint grid) {int n grid.size();vectorvectorint d(n, vectorint(n, INT_MAX));for (int i 0; i n; i) {d[0][i] grid[0][i];}for (int i 1; i n; i) {for (int j 0; j n; j) {for (int k 0; k n; k) {if (j k) {continue;}d[i][j] min(d[i][j], d[i - 1][k] grid[i][j]);}}}int res INT_MAX;for (int j 0; j n; j) {res min(res, d[n - 1][j]);}return res;}
};五、解题思路
(1) 使用动态规划来解决问题。
