代码编织梦想

题目

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

示例 1:

输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示:

  • 0 < grid.length <= 200
  • 0 < grid[0].length <= 200

Related Topics

  • 数组
  • 动态规划
  • 矩阵

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

动态规划

转移方程:

  1. i=0 且 j=0 时,为起始元素;
  2. i=0 且 j\=0 时,为矩阵第一行元素,只可从左边到达;
  3. i=0 且 j=0 时,为矩阵第一列元素,只可从上边到达;
  4. i\=0 且 j\=0 时,可从左边或上边到达;

d p ( i , j ) = { g r i d ( i , j ) , i = 0 , j = 0 g r i d ( i , j ) + d p ( i , j − 1 ) , i = 0 , j ≠ 0 g r i d ( i , j ) + d p ( i − 1 , j ) , i ≠ 0 , j = 0 g r i d ( i , j ) + max ⁡ [ d p ( i − 1 , j ) , d p ( i , j − 1 ) ] , i ≠ 0 , j ≠ 0 dp(i,j)= \begin{cases} grid(i,j) & {,i=0, j=0}\\ grid(i,j) + dp(i,j-1) & {,i=0, j \ne 0}\\ grid(i,j) + dp(i-1,j) & {,i \ne 0, j=0}\\ grid(i,j) + \max[dp(i-1,j),dp(i,j-1)]& ,{i \ne 0, j \ne 0} \end{cases} dp(i,j)= grid(i,j)grid(i,j)+dp(i,j1)grid(i,j)+dp(i1,j)grid(i,j)+max[dp(i1,j),dp(i,j1)],i=0,j=0,i=0,j=0,i=0,j=0,i=0,j=0

题解

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length,n = grid[0].length;
        for (int i = 0;i < m;i ++){
            for (int j = 0;j < n;j++){
                if (i == 0 && j == 0) continue;
                if (i == 0) grid[i][j] += grid[i][j-1];
                else if (j == 0) grid[i][j] += grid[i-1][j];
                else grid[i][j] += Math.max(grid[i][j-1],grid[i-1][j]);
            }
        }
        return grid[m-1][n-1];
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_52476654/article/details/126099825

剑指offer(47):礼物的最大值(动态规划详解,python版)_独孤呆博的博客-爱代码爱编程_礼物的最大值

本博客主要内容为图书《剑指offer》第二版47 题的解题思路及代码。方法可能还有不足之处,欢迎大家讨论评论。 1. 题目描述   在一个 m*n 的棋盘中的每一个格都放一个礼物,每个礼物都有一定的价值(价值大

剑指offer第二版面试题47:礼物的最大价值(java)_许文杰的博客-爱代码爱编程

题目描述: 在一个m×n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格直到到达棋盘的右下角。给定一个棋盘及其上面的礼物,请计算你最多能

动态规划之棋盘路径问题_guangcheng0312q的博客-爱代码爱编程

动态规划之棋盘路径问题 1.对比 DP vs 回溯 vs 贪心 回溯(递归) - 重复计算贪心 - 永远局部最优DP - 记录局部最优子结构/多种记录值 2.棋盘路径问题 问题描述: 如下图所示,小人从左上角移动到右下角,总共有多少种走法. 约束条件为:粉红色为石头,走不通,小人走路方向只有向下与向右.

剑指offer47 礼物的最大价值_a282608054的博客-爱代码爱编程

题目描述 在一个 m*n 的棋盘的每一个格都放有一个礼物,每个礼物都有一定价值(大于 0)。从左上角开始拿礼物,每次向右或向下移动一格,直到右下角结束。给定一个棋盘,求拿到礼物的最大价值。例如,对于如下棋盘 1 10 3

礼物的最大价值(Java)-爱代码爱编程

礼物的最大价值(Java) 题目:在一个m*n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于0)。 你可以从棋盘的 左上角开始拿格子里的礼物,并每次向右或者向下移动一格,直到到达棋盘的右下角。给定一个棋盘及其上面的礼物,请计算你最多能拿到多少价值的礼物。代码: /** * @desc 礼物的最大价值 * @author zhaol

礼物的最大价值--剑指offer(JAVA)-爱代码爱编程

题目: 在一个 m*n 的棋盘中的每一个格都放一个礼物,每个礼物都有一定的价值(价值大于0).你可以从棋盘的左上角开始拿各种里的礼物,并每次向右或者向下移动一格,直到到达棋盘的右下角。给定一个棋盘及上面个的礼物,请计算你最多能拿走多少价值的礼物? 思路: 我们利用递归的思路来分析。定义函数f(i,j)表示到达坐标为(i,j)的格子时能拿到的礼物总和的最大值

剑指 Offer 47. 礼物的最大价值Java题解-爱代码爱编程

好的到了新的一学期复习的时候,我动态规划又几乎不会了,算法能力小于上学期。。 面试前复习剑指Offer路过,经过写题练习,这种简单的动态规划已经会了。看到下面的话,原来我当时这都不会哈哈哈哈,加油!以后看现在觉得难的东西应该也会觉得简单吧。 二刷路过,这次也想不到。只能想到dfs,还没下手就去看看别人的题解,原来用动态规划,盒盒盒。 1.思路 设f

打卡系列-剑指 Offer 47. 礼物的最大价值-爱代码爱编程

在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物? 示例 1: 输入:  [   [1,3,1],   [1,5,1],   [4,2,1] ] 输出: 12

LeetCode:剑指 Offer 47.礼物的最大价值(C语言)-爱代码爱编程

题目描述: 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物? 示例 1: 输入: [ [1,3,1], [1,5,1], [4,2,1] ]

剑指offer 面试题47:礼物的最大值(java)-爱代码爱编程

题目 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物? 示例 1: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12

背包内物品价值最大java_背包笔记及Java实现-爱代码爱编程

推荐背包九讲,非常棒。以下是个人对其前四讲内容的梳理和Java实现,用于快速回顾知识点。 01背包 问题: N件物品,一个容量M的背包。A[]是物品体积,V[]是物品价值,求背包能装物品的最大价值。 思路: dp[i][j]表前i件物品在容量最大为j的限制下能得到的最大价值。 public int pack01Solution1(int

剑指 Offer 47. 礼物的最大价值-爱代码爱编程

LeetCode - 剑指 Offer 47. 礼物的最大价值 题目描述分析代码总结 题目描述 难度:中等 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价

【剑指 Offer】47. 礼物的最大价值(详细解析!)-爱代码爱编程

第 9 日:礼物的最大价值 题目链接:https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/ 题目 在一个 m*n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个

剑指Offer 47.礼物的最大值-爱代码爱编程

在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物? 示例 1: 输入:  [   [1,3,1],   [1,5,1],   [4,2,1] ] 输出: 1

礼物的最大价值(中等)-爱代码爱编程

题目描述 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物? 示例   输入: [   [1,3,1],   [1,5,1],   [4

剑指offer-JZ47 礼物的最大价值(Java版)-爱代码爱编程

描述 在一个m\times nm×n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物? 如输入这样的一个二维数组, [ [1,3,1], [1,5,1], [4,2,1

剑指 Offer 47. 礼物的最大价值-动态规划-爱代码爱编程

起点:矩阵左上角 终点:矩阵右下角 只能向下或向右,求礼物总价值最大的路径 状态定义:dp[i][j]表示从矩阵左上角开始,到(i,j)时拿到的礼物最大累计价值 转移方程: i = 0,j = 0,起始元素 i = 0,j != 0,为矩阵第一行元素,只能向右移动dp[i][j] = dp[i][j-1] + grid[i][j] i != 0,j =

剑指Offer47—礼物的最大价值-爱代码爱编程

力扣 题意 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?   解题思路 根据题目说明,易得某单元格只可能从上边单元格或左边单元格到达。 设 f(i

java礼物的最大价值_bupt_jtc的博客-爱代码爱编程

        在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物? class Solution { public int maxValue(int[][

剑指offer 47:礼物的最大价值_剑指 offer 47. 礼物的最大价值-爱代码爱编程

题目描述:         在一个m×n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物? 如输入这样的一个二维数组, [ [1,3,1], [1,5,1], [4,2