1289.下降路径最小和 II:通俗易懂地讲解O(n^2) + O(1)的做法
【LetMeFly】1289.下降路径最小和 II:通俗易懂地讲解O(n^2) + O(1)的做法
力扣题目链接:https://leetcode.cn/problems/minimum-falling-path-sum-ii/
给你一个 n x n
整数矩阵 arr
,请你返回 非零偏移下降路径 数字和的最小值。
非零偏移下降路径 定义为:从 arr
数组中的每一行选择一个数字,且按顺序选出来的数字中,相邻数字不在原数组的同一列。
示例 1:
输入:arr = [[1,2,3],[4,5,6],[7,8,9]] 输出:13 解释: 所有非零偏移下降路径包括: [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9] 下降路径中数字和最小的是 [1,5,7] ,所以答案是 13 。
示例 2:
输入:grid = [[7]] 输出:7
提示:
n == grid.length == grid[i].length
1 <= n <= 200
-99 <= grid[i][j] <= 99
方法一:动态规划
这道题其实思路很简单:
- gird[i][j]来自gird[i - 1]的哪一个?当然是gird[i - 1]中最小的那一个。
- 如果grid[i - 1]中最小的那个元素恰好是j怎么办?那么gird[i][j]就来自gird[i - 1]中第二小的那一个。
不难发现,我们只关注上一行最小的两个元素(的位置)
具体实现
写一个函数findMin2(v)
,用来寻找数组v中最小的两个元素的位置。
用$i$从第2行开始遍历地图grid:
- 用$j$遍历$gird[i]$:
- 如果$j$等于上一行最小元素的下标:$grid[i][j] += grid[i - 1][第二小元素的下标]$
- 否则$grid[i][j] += grid[i - 1][最小元素的下标]$
最终返回最后一行的最小元素即可。
- 时间复杂度$O(n^2)$,其中$size(gird) = n\times n$
- 空间复杂度$O(1)$
AC代码
C++
1 |
|
Python
1 |
|
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/132201281
1289.下降路径最小和 II:通俗易懂地讲解O(n^2) + O(1)的做法
https://blog.letmefly.xyz/2023/08/10/LeetCode 1289.下降路径最小和II/