TaylorSwift13
2023-09-14 20:41 广州城市职业学院 Java
关注
T3 矩阵路径最大和
如果题目没有乘2的条件，我们用dp计算一遍，记录左上角到当前元素的最大和，然后取最后一个元素即可。现在有了乘2的条件，如果动了一个元素，那么答案有两种情况：一种是经过这个元素，一种是不经过。为了快速求出经过这个元素的情况，我们从右下角再计算一遍，记录右上角到当前元素的最大和，与前面的左上角到当前的最大和相加即可。而如果不经过该元素还能最大，那就是之前的情况了，二者取大者即可。
时间复杂度O(m*n)，空间复杂度O(m*n)
查看原帖
6 2
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 校招生月薪1W算什么水平 #
27439次浏览 169人参与
# 硬件人的简历怎么写 #
311735次浏览 3057人参与
# “vivo”个offer #
36573次浏览 277人参与
# 我是面试官，请用一句话让我破防 #
23074次浏览 118人参与
# 工作后明白的那些道理 #
20951次浏览 220人参与
# 如果上班像打游戏，你最想解锁什么技能 #
7102次浏览 67人参与
# 中美关税战对我们有哪些影响 #
41457次浏览 351人参与
# 中美关系回暖，你会选择出海吗？ #
4925次浏览 95人参与
# AI时代，哪些岗位最容易被淘汰 #
2674次浏览 27人参与
# 华为保温 #
106126次浏览 403人参与
# 机械人，签完三方你在忙什么？ #
65651次浏览 244人参与
# 第一份工作应该只看薪资吗 #
192215次浏览 1687人参与
# 牛友们，签完三方你在忙什么？ #
119856次浏览 958人参与
# 哪些行业值得去? #
4550次浏览 46人参与
# 金融财经春招备战日记 #
38674次浏览 210人参与
# i人适合做什么工作 #
10010次浏览 88人参与
# 如果秋招能重来，我会____ #
34395次浏览 283人参与
# 美团开奖 #
209038次浏览 1103人参与
# 国央企笔面经互助 #
161106次浏览 1182人参与
# 读研or工作，哪个性价比更高？ #
77110次浏览 767人参与
# 华为池子有多大 #
109570次浏览 750人参与