- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/minimum-falling-path-sum/description/
Given a square array of integers A
, we want the minimum
sum of a falling path through A.
Afalling path starts at any element in the first row, and chooses one element from each row. The next row's choice must be in a column that is different from the previous row's column by at most one.
Example 1:
Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation:
The possible falling paths are:
Thefalling path with the smallest sum is [1,4,7]
, so the answer is 12
.
Note:
1、 1<=A.length==A[0].length<=100
;
2、 -100<=A[i][j]<=100
;
从最上面一行开始向下走,每次移动的时候最多只可以移动一列。也就是说每次必须向下走一行,列可以不变、也可以向左右移动一列。求到达最后一行的时候,最短的路径长度。
刚做过类似的题目,但是我还是没有做出来。。这个题和799香槟塔很像,都是二维空间求最大、最小的路径问题。
如果看上面这个图就明白了,数组中每个位置都要从上一层获得三个相邻列的最小值,换句话说,每个位置都可以给下面三个相邻列传递最小值。那么,其实就是一个动态规划嘛,到每个位置的最短路径,就是当前数值加上到达上面那层的三个相邻列的最小值。
所以这个题代码其实很简单,只需要设置好边界,然后我们每次查找上面的三个最小值加上当前的位置,得到的就是到达当前位置的最小路径。
做DP的时候,不要怕设置边界条件。我以前总想着用各种方法想着让dp数组和原来的数组一样大,这个思想是错误的!因为我们记忆化搜索的时候实际上有很多边界条件的,其实是可以转化成dp的边界条件,或者说是初始条件。提前给dp数组设定各种边界条件,能简化很多状态转移代码~这个题就很好的说明了这点!
时间复杂度是O(MN),空间复杂度是O(MN)。
class Solution(object):
def minFallingPathSum(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
M, N = len(A), len(A[0])
dp = [[0] * (N + 2) for _ in range(M)]
for i in range(M):
dp[i][0] = dp[i][-1] = float('inf')
for j in range(1, N + 1):
dp[i][j] = A[i][j - 1]
for i in range(1, M):
for j in range(1, N + 1):
dp[i][j] = A[i][j - 1] + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1])
return min(dp[-1])
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
799. Champagne Toweropen in new window【面试现场】如何编程获得最多的年终红包奖?open in new window
https://leetcode.com/problems/minimum-falling-path-sum/discuss/186689/Java-DP-solution-with-graph-illustrated-explanations
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我有这个示例代码: #include #include int main() { Eigen::MatrixXf M = Eigen::MatrixXf::Random(1000, 1000)
我有一个像这样的数据框: +-----+--------+ |count| country| +-----+--------+ | 12| Ireland| | 5|Thailand| +-
我想要 SUM(tot_bill_1+tot_bill_2) AS 总计,但这不起作用 SELECT *, IF(SUM(bill_1) IS NULL, '99', SUM(bill_1)) AS
如果我们有两个矩阵 X 和 Y,都是二维的,现在在数学上我们可以说:sum(X-Y)=sum(X)-总和(Y). Matlab 哪个效率更高?哪个更快? 最佳答案 在我的机器上,sum(x-y) 对于
我正在运行 Hive 1.1.0 并看到对于两个 bigint 列,active_users 和 inactive_users,SUM(active_users + inactive_users) <
是否可以在一个选择查询中求和? 类似这样的事情: SELECT id, SUM(current_price - bought_price)*amount AS profit FROM purchase
这是一个相当奇怪的结果。我希望这些具有相同的产量。 下面还有从数据库中提取的 excel 链接。 https://twentius.opendrive.com/files?89038281_muoyg
我必须对 2 个字段求和,然后再求和。从性能的角度来看,先添加字段还是在对列求和之后添加字段有什么区别? 方法 1 = SELECT SUM(columnA + columnB) 方法 2 = SEL
这是一个经典问题,但我很好奇是否有可能在这些条件下做得更好。 问题:假设我们有一个长度为4*N的排序数组,即每个元素重复4次。请注意,N 可以是任何自然数。此外,数组中的每个元素都受制于 0 A. 执
我正在编写一个 Pig 程序,该程序加载一个用制表符分隔整个文件的文件 例如:名称 TAB 年份 TAB 计数 TAB... file = LOAD 'file.csv' USING PigStora
我有一个包含以下字段的表: EmpID, Code, Amount, TransDate, CM, CMDate 我想要进入数据网格的是 SUM所有的Amount具有相同的 Code和 SUM CM具
我有两个单独的查询用于提取报告信息。一年效果很好。但是,如果一个月超过 1 年,则不会显示正确的响应。 这是我的两个查询: select SUM(rpt_complete.total) total,
我想查询一个团队的积分。通过在列上执行 SUM + 来自具有相同团队 ID 的另一个表的 SUM 来添加这些点。我试着这样写: SELECT k.id, s.fylke, s.
这个问题在这里已经有了答案: How to deal with floating point number precision in JavaScript? (47 个回答) Unexpected
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎与 help center 中定义的范围内的编程无关。 . 关闭 5 年前。 Improve
我已经找了一段时间,但找不到这个问题的答案(也许我没有搜索正确的术语或其他东西)。基本上,我有一个数据库,每个日期有任意数量的条目。我需要取包含条目的最后 X 天的总和(忽略没有条目的天数)。我知道如
我正在尝试获取 B 行中包含 A 行中某个值的所有值中的一些值。我猜这个问题很简单。 这是我的查询: =QUERY('Sheet1'!$A$16:D, "Select sum(D) Where C c
我正在尝试运行以下查询,但出现以下错误: You have an error in your SQL syntax; check the manual that corresponds to your
我有一个 tableA,其中包含以下结构 我将此结构修改为如下所示的tableB,以减少行数,并且类别是固定长度的 假设我在 tableA 中修改为新结构后有 210 万条数据,tableB 仅包含
我的表在 Postgres 中的数据: id user_id sell_amount sell_currency_id buy_amount buy_currency_id type
我是一名优秀的程序员,十分优秀!