关注
T3 矩阵路径最大和
如果题目没有乘2的条件,我们用dp计算一遍,记录左上角到当前元素的最大和,然后取最后一个元素即可。现在有了乘2的条件,如果动了一个元素,那么答案有两种情况:一种是经过这个元素,一种是不经过。为了快速求出经过这个元素的情况,我们从右下角再计算一遍,记录右上角到当前元素的最大和,与前面的左上角到当前的最大和相加即可。而如果不经过该元素还能最大,那就是之前的情况了,二者取大者即可。
时间复杂度O(m*n),空间复杂度O(m*n)
查看原帖
6 2
相关推荐
10-27 10:59
门头沟学院 FPGA工程师 点赞 评论 收藏
分享
10-12 14:31
广东药科大学 Java 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 校招生月薪1W算什么水平 #
33430次浏览 188人参与
# 哪一瞬间觉得自己长大了 #
38104次浏览 493人参与
# “vivo”个offer #
38545次浏览 280人参与
# 我是面试官,请用一句话让我破防 #
26299次浏览 128人参与
# vivo工作体验 #
27788次浏览 124人参与
# 如果上班像打游戏,你最想解锁什么技能 #
8009次浏览 70人参与
# 工作后明白的那些道理 #
21602次浏览 225人参与
# 一人一个landing小技巧 #
123736次浏览 1441人参与
# 实习最想跑路的瞬间 #
87322次浏览 542人参与
# 中美关税战对我们有哪些影响 #
42794次浏览 361人参与
# 机械制造2023笔面经 #
149425次浏览 840人参与
# 如果重来一次你还会读研吗 #
201485次浏览 1932人参与
# AI时代,哪些岗位最容易被淘汰 #
3228次浏览 27人参与
# 中美关系回暖,你会选择出海吗? #
6480次浏览 107人参与
# 华为保温 #
107380次浏览 406人参与
# 哪些行业值得去? #
5222次浏览 50人参与
# i人适合做什么工作 #
11246次浏览 97人参与
# 美团开奖 #
220913次浏览 1142人参与
# 读研or工作,哪个性价比更高? #
78109次浏览 768人参与
# 如果秋招能重来,我会____ #
37064次浏览 299人参与
# 华为池子有多大 #
110384次浏览 750人参与
