第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
Minimum Dropping Path Sum

题目描述

You are given a two-dimensional list of integers matrix. Return the minimum sum you can get by taking a number in each row with the constraint that any row-adjacent numbers cannot be in the same column.
Constraints
1 ≤ n ≤ 250 where n is the number of rows in matrix
2 ≤ m ≤ 250 where m is the number of columns in matrix
Example 1
Input
matrix = [
[4, 5, -2],
[2, 6, 1],
[3, 1, 2]
]
Output
1
Explanation
We can take -2 from the first row, 2 from the second row, and 1 from the last row.
Example 2
Input
matrix = [
[3, 0, 3],
[2, 1, 3],
[-2, 3, 0]
]
Output
1
Explanation
We can take 0 from the first row, 3 from the second row, and -2 from the last row.

前置知识

公司

  • 暂无

思路

这道题是不同路径(或者杨辉三角)的换皮题。
这道题是让我们每一行选择一个数,使得数字和最小。唯一的限制是相邻行拿的数字不能列相同(其实就是不能上下紧挨着拿)。
一个可能的暴力思路是:
  • 先取第一行。第一行有 n (n 为列数)个选择,那就挨个试。
  • 接下来取第二行。第二行有 n-1 个选择,那就挨个试。
  • 接下来取第三行。第三行有 n-1 个选择,那就挨个试。
  • 。。。
不要小看暴力法, 这是一种解决问题的思维习惯。
如果你将上面的过程画成一棵树的话,那么可以看出时间复杂度大概是和底层的节点数是一个数量级的,是指数级别的。就算不画树,你也不难看出大概的计算次数是 n (n -1) (n - 1) ...(一共 m - 1 个 n -1)。那么我们可以优化么?
实际上是可以的。我们先不考虑题目的限制”相邻行拿的数字不能列相同“。那么我们的策略就变成了贪婪, 只要每一行都取最小的不就行了?时间复杂度是 $O(m * n)$。
那么加上这个限制会有什么不同么?以题目的例子为例:
matrix = [
[3, 0, 3],
[2, 1, 3],
[-2, 3, 0]
]
贪心的做法第一行要选 0,第二行要选 1,不过违反了限制。那我们有必要把所有的选择第一行和第二行的组合计算出来么(就像上面的暴力法那样)?其实我们只记录上一行的最小和次小值即可。如果出现了上面的情况,那么我们可以考虑:
  • 选择 1 和上一行次小值(3 + 1)
  • 选择行次小值和上一行最小值(2 + 0)
剩下的逻辑也是如此。
最终我们返回选择到达最后一行的最小值即可。

代码

代码支持:Python3
Python3 Code:
class Solution:
def solve(self, matrix):
dp = [(0, -1)]
m, n = len(matrix), len(matrix[0])
for i in range(m):
next_dp = [(float("inf"), -1), (float("inf"), -1)]# (smallest, 2nd smallest)
for j in range(n):
for v, k in dp:
if k == j:
continue
nxt = matrix[i][j] + v
if nxt < next_dp[0][0]:
next_dp = [(nxt, j), next_dp[0]]
elif nxt < next_dp[1][0]:
next_dp[1] = (nxt, j)
break
dp = next_dp # rolling array
return dp[0][0]
复杂度分析
  • 时间复杂度:$O(m*n)$
  • 空间复杂度:$O(1)$ (使用了滚动数组优化)

相关题目

  • Painting-Houses (换皮题。代码一模一样,直接复制粘贴代码就可以 AC)
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。