我要招人

去企业版

首页 > 试题广场 >

牛妹的礼物

[编程题]牛妹的礼物

热度指数：10600 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

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

地板是 $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

算法知识视频讲解

zhouleilei

发表于 2020-03-23 10:23:42

一、思路：用一个矩阵dp来保存走到每个格子的时候，当前格子累计的礼物的最小体积，dp的大小和格子的大小一致，也是N*M的矩阵。二、图示：三、详细流程： 1、dp第0行和第0列的初始化； 2、dp的更展开全文

吃芝士的培根

发表于 2020-07-30 13:34:01

简单的动态规划，直接走就行了，第一行的数据只能右边走所以数据只跟左边的数据有关第一列的数据只能从上面往下走，只跟上面数据有关其他的方面可以来自三个方向，上面，下面，左上 public class Solution { /** * * @param presentVolu 展开全文

王清楚

发表于 2020-08-18 15:40:21

用表示到达第行第列的最小和。第一行和第一列单独考虑：对于第一行的位置，肯定是从转移过来的。对于第一列的位置，肯定是从转移过来的。对于其他位置来说，可能是从上边，左边，左上方过来的，所以有了状态转移方程 #include<iostream> #include& 展开全文

Maokt

发表于 2021-07-30 16:04:48

算法思想一：动态规划解题思路：简单的动态规划，直接走就行了， 1、当只有一行的数据只能右边走所以数据只跟左边的数据有关 2、当只有一列的数据只能从上面往下走，只跟上面数据有关 3、其他情况可以来自三个方向，上面，下面，左上来计算算法流程： 1、两层遍历矩阵 row属于展开全文

Miss.Zhou

发表于 2020-02-05 20:26:00

简单的不能再简单的dp了但有时很经典啊。。。作为面向大众普通同学的题库来说，也是要会的啊。。。要是非要再白痴的做法难不成是把所有方案遍历一遍？真的没有更简单的dp了QAQ 让我写简单做法真的找不到了QAQ 所有方案遍历一遍更麻烦啊 QAQ因为是简单题，所以不想在空间时间复杂度上做文章 class 展开全文

小兄弟加油啊

发表于 2021-10-08 16:31:04

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 & 展开全文

认认真真coding

发表于 2021-08-01 15:17:34

题目描述众所周知，牛妹有很多很多粉丝，粉丝送了很多很多礼物给牛妹，牛妹的礼物摆满了地板。地板是N×M的格子，每个格子有且只有一个礼物，牛妹已知每个礼物的体积。地板的坐标是左上角(1,1) 右下角（N, M）。牛妹只想要从屋子左上角走到右下角，每次走一步，每步只能向下走一步或者向右走一步或者向右下走展开全文

摸鱼学大师

发表于 2021-07-31 14:42:58

思路：题目的主要信息：矩阵不为空，且矩阵中的内容非负数总体上要从矩阵的左上角到右下角，每次可以选择向下、向右、向右下三个方向路过矩阵每个格子中的数累加，求最短路径和事实上，这道题就是一个求矩阵最短路径和的问题，只不过它是有三个方向可以选择。方法一：递归（超时）具体做法：容易想到的是，展开全文

牛一霸

发表于 2021-08-16 23:04:50

题目：牛妹的礼物描述：众所周知，牛妹有很多很多粉丝，粉丝送了很多很多礼物给牛妹，牛妹的礼物摆满了地板。地板是N×M的格子，每个格子有且只有一个礼物，牛妹已知每个礼物的体积。地板的坐标是左上角(1,1) 右下角（N, M）。牛妹只想要从屋子左上角走到右下角，每次走一步，每步只能向下走一步或者向右走一展开全文