首页 > 试题广场 >

礼物的最大价值

[编程题]礼物的最大价值

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

在一个 $m\times n$ 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

如输入这样的一个二维数组，
[
[1,3,1],
[1,5,1],
[4,2,1]
]

那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为12

示例1

输入

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

输出

备注:

算法知识视频讲解

牛客题解官

发表于 2022-04-25 18:56:20

精华题解题目的主要信息：一个m∗nm*nm∗n的棋盘中每个格子都有一个礼物，价值各自记录在矩阵中需要从棋盘左上角走到右下角，经过某个格子，该格子记录的价值就累加每次只能往下或者往右，求能够获得的最大价值举一反三：学习完本题的思路你可以解决如下题目： JZ70. 矩形覆盖 JZ63. 买卖股票的展开全文

apple爆了

发表于 2021-11-25 17:11:39

一般的路劲问题一层一层遍历就行了 public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param grid int整型vector<vector<>> 展开全文

香芋派丶

发表于 2021-12-14 20:51:26

动态规划 ①确定状态：设走到格子 grid[x,y] 时，能获得的最大价值为 f(x,y)。分析最后一步，即走到了右下角 grid[m,n]，根据题意，其上一步只能是 grid[m-1,n] 或 grid[m,n-1]，那么为了获得最大价值的礼物，此时就会选择能够获得价值较大的那一项作为上一步，展开全文

designeer

发表于 2021-11-12 10:35:25

class Solution: def maxValue(self , grid ): # wr 展开全文

ch_98

发表于 2022-01-28 12:06:00

由于只能方向向右或者向下，因此第m行第n列的值只能来自于m-1行n列或者m行n-1列再加上grid[m][n],所以可知maxSum[i][j] = Math.max(maxSum[i - 1][j], maxSum[i][j - 1]) + grid[i - 1][j - 1]; public 展开全文