TaylorSwift13
2023-09-14 20:41 广州城市职业学院 Java
关注
T3 矩阵路径最大和
如果题目没有乘2的条件，我们用dp计算一遍，记录左上角到当前元素的最大和，然后取最后一个元素即可。现在有了乘2的条件，如果动了一个元素，那么答案有两种情况：一种是经过这个元素，一种是不经过。为了快速求出经过这个元素的情况，我们从右下角再计算一遍，记录右上角到当前元素的最大和，与前面的左上角到当前的最大和相加即可。而如果不经过该元素还能最大，那就是之前的情况了，二者取大者即可。
时间复杂度O(m*n)，空间复杂度O(m*n)
查看原帖
6 2
相关推荐
投递快手等公司10个岗位 > 点赞 评论 收藏
分享
查看11道真题和解析 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 腾讯音乐求职进展汇总 #
57401次浏览 343人参与
# 你的秋招第一面感觉怎么样 #
61623次浏览 504人参与
# 牛友故事会 #
320156次浏览 8623人参与
# 互联网公司评价 #
349412次浏览 3639人参与
# 互联网回暖，腾讯要招5000+人！ #
259262次浏览 4877人参与
# 怎么防止在试用期被辞退 #
110402次浏览 850人参与
# 秋招投简历越早越好吗 #
61113次浏览 605人参与
# 百度工作体验 #
188487次浏览 1845人参与
# 国企vs私企，怎么选？ #
18221次浏览 157人参与
# 我在牛爱网找对象 #
161835次浏览 1225人参与
# 盲审过后你想做什么？ #
9782次浏览 93人参与
# 面试等了一周没回复，还有戏吗 #
101442次浏览 938人参与
# 当下环境，你会继续卷互联网，还是看其他行业机会 #
90048次浏览 672人参与
# 聊聊这家公司值得去吗 #
195632次浏览 2061人参与
# 职业发展规划如何回答 #
29672次浏览 167人参与
# 没有实习经历还能找到好工作吗？ #
6866次浏览 38人参与
# 25届网易互娱暑实进度 #
63052次浏览 603人参与
# 你认为工作的意义是什么 #
120285次浏览 910人参与
# 实习要如何选择和准备？ #
20619次浏览 377人参与
# 你的办公桌上都有什么？ #
3643次浏览 29人参与