TaylorSwift13
2023-09-14 20:41 广州城市职业学院 Java
关注
T3 矩阵路径最大和
如果题目没有乘2的条件，我们用dp计算一遍，记录左上角到当前元素的最大和，然后取最后一个元素即可。现在有了乘2的条件，如果动了一个元素，那么答案有两种情况：一种是经过这个元素，一种是不经过。为了快速求出经过这个元素的情况，我们从右下角再计算一遍，记录右上角到当前元素的最大和，与前面的左上角到当前的最大和相加即可。而如果不经过该元素还能最大，那就是之前的情况了，二者取大者即可。
时间复杂度O(m*n)，空间复杂度O(m*n)
查看原帖
6 2
相关推荐
点赞 评论 收藏
分享
牛至超人：我的脚痒了 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 赚钱的意义在这一刻具象化 #
7608次浏览 177人参与
# 快手年终开大包 #
1655次浏览 38人参与
# 今年春招是金一银二嘛？ #
15485次浏览 182人参与
# AI求职实录 #
9143次浏览 272人参与
# 没关系，至少我的__很曼妙 #
6693次浏览 123人参与
# 初创公司值得加入吗？ #
37427次浏览 217人参与
# 抛开难度不谈，你最想去哪家公司？ #
8643次浏览 166人参与
# 为什么有人零实习也能进大厂？ #
8612次浏览 189人参与
# 牛客吐槽大会 #
6095次浏览 115人参与
# 1月小结：你过的开心吗？ #
3155次浏览 62人参与
# AI时代的工作 VS 传统时代的工作，有哪些不同？ #
11356次浏览 270人参与
# 你的第一家实习公司是什么档次？ #
6693次浏览 97人参与
# 当你问AI“你会取代我的工作吗”，它说_？ #
5749次浏览 175人参与
# 你的landing期是如何度过的？ #
11774次浏览 226人参与
# 除了Java，最推荐学什么技术？ #
9495次浏览 201人参与
# 你今年的平均薪资是多少？ #
200969次浏览 1012人参与
# 如果能重来，就业or读研你选哪个？ #
270463次浏览 2601人参与
# 机械人你知道哪些单休企业 #
83458次浏览 417人参与
# 你觉得什么岗位会被AI替代 #
37448次浏览 256人参与
# 秋招结束之后的日子 #
117327次浏览 1062人参与