礼物的最大价值问题,2个人拿

网易笔试


基础题是这个,礼物的最大价值,很简单,动规直接搞定

但是这个是拿一次的方案

现在是说有2个人,同时开始拿,问2个人从左上到右下走一次加起来最多能拿多少

我觉得2个人同时拿和每个人依次拿是一样的,就是第一个先走一次,第二个再走一次,然后把两个人的结果加起来即可。

我的思路是:

第一个人先走,记录拿的路径,然后把路径上的礼物价值置为0

第二个人再拿。

拿完以后两个人结果相加即可。但是这样只A了60%,感觉思路没问题,求大佬们指教
#网易##笔试题目#
全部评论
每次都拿最大的不一定结果最优,因为每个人只能往右或者往下走,并不能回头。 这道题可以两个人一起动态规划,dp(i,j,k,l)表示第一个人在i j 第二个人在k l的最大价值,dp(i j k l)的上一个状态是两个人分别在上面的格子或者左边的格子,总共四种可能取一个最大值然后加上(i j)和(k l)格子里的价值就行。
2 回复 分享
发布于 2022-03-05 18:53
第一次穷举第二次dp
点赞 回复 分享
发布于 2022-03-05 18:41
这样不太行,我也这样写的。 但是第一次不一定是拿最大的价值,
点赞 回复 分享
发布于 2022-03-05 18:20
思路一样,也没ac
点赞 回复 分享
发布于 2022-03-05 17:59

相关推荐

zygg:拼多多挂是不是过一两天就挂的呀
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客企业服务