T3 矩阵路径最大和 如果题目没有乘2的条件,我们用dp计算一遍,记录左上角到当前元素的最大和,然后取最后一个元素即可。现在有了乘2的条件,如果动了一个元素,那么答案有两种情况:一种是经过这个元素,一种是不经过。为了快速求出经过这个元素的情况,我们从右下角再计算一遍,记录右上角到当前元素的最大和,与前面的左上角到当前的最大和相加即可。而如果不经过该元素还能最大,那就是之前的情况了,二者取大者即可。 时间复杂度O(m*n),空间复杂度O(m*n)
6 2

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务