首页 > 试题广场 >

牛妹的礼物

[编程题]牛妹的礼物

众所周知，牛妹有很多很多粉丝，粉丝送了很多很多礼物给牛妹，牛妹的礼物摆满了地板。

地板是 $N\times M$ 的格子，每个格子有且只有一个礼物，牛妹已知每个礼物的体积。

地板的坐标是左上角(1,1) 右下角（N, M）。

牛妹只想要从屋子左上角走到右下角，每次走一步，每步只能向下走一步或者向右走一步或者向右下走一步

每次走过一个格子，拿起（并且必须拿上）这个格子上的礼物。

牛妹想知道，她能走到最后拿起的所有礼物体积最小和是多少？

示例1

输入

[[1,2,3],[2,3,4]]

先走到(1,1)这个点，此时和为1，然后走到(1,2)这个点，拿起(1,2)点的数字，此时和为3，最后走到(2,3)，拿起(2,3)点的数字，此时和为7

0<N,M<300
0<=每个礼物的体积<100

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

动态规划

难度：

0条回答 26收藏 5657浏览

查看代码

扫一扫，把题目装进口袋