首页 > 试题广场 >

礼物的最大价值

[编程题]礼物的最大价值
  • 热度指数：30494 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
在一个的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 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]]

输出

12

备注:
算法知识视频讲解
添加回答
Java
pein531头像 pein531 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型二维数组 
     * @return int整型
     */
    public int maxValue (int[][] grid) {
        // write code here
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; 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 - 1][j], grid[i][j - 1]);    // 其他情况选择从上和从左来中更大的那个
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

发表于 2021-11-20 23:03:39 回复(0)
Java
小蒙啊头像 小蒙啊 
//二维动态规划，创建一个dp二维数组，长度比grid大一
//dp中存放对应的grid数组中走到这个位置的礼物最大价值，
//状态转移方程：
//dp[i][j] = Math.max( dp[i-1][j] + grid[i-1][j-1], dp[i][j-1] + grid[i-1][j-1])
import java.util.*;

public class Solution {
    public int maxValue (int[][] grid) {
        int[][] dp = new int[grid.length+1][grid[0].length+1];
        for(int i = 1; i < dp.length ; i++){
            for(int j = 1 ; j < dp[0].length ; j++){
                dp[i][j] = Math.max(dp[i-1][j]+grid[i-1][j-1],dp[i][j-1]+grid[i-1][j-1]);
            }
        }
        return dp[grid.length][grid[0].length];
    }
}

发表于 2022-01-27 22:05:24 回复(0)
Python 3
kinter1头像 kinter1 
class Solution:
    def maxValue(self , grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] + grid[i][0]
        for i in range(1, n):
            dp[0][i] = dp[0][i - 1] + grid[0][i]
        for i in range(1, m):
            for j in range(1, n):
                if i < m and j < n:
                    dp[i][j] = max(dp[i][j - 1] + grid[i][j], dp[i - 1][j] + grid[i][j])
        return dp[m - 1][n - 1]

发表于 2022-03-02 11:45:25 回复(0)
有点心碎1头像 有点心碎1 
function maxValue(grid) {
    // write code here
    let n = grid.length;
    let m = grid[0].length;
    let dp = [];
    for (let i = 0; i < n; i++) {
        dp[i] = [];
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (j === 0 && i === 0) {
                dp[i][j] = grid[0][0];
            } else if (i === 0) {
                dp[i][j] = dp[i][j - 1] + grid[i][j];
            } else if (j === 0) {
                dp[i][j] = dp[i - 1][j] + grid[i][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
    }
    return dp[n - 1][m - 1];
}

发表于 2023-03-14 18:06:40 回复(0)
C++
Spectre_头像 Spectre_ 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int maxValue(vector<vector<int> >& grid) {
        // 时间复杂度O(N^2)，空间复杂度O(N^2)
        int dp[grid.size()][grid[0].size()];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < grid.size(); ++i) dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int j = 1; j < grid[0].size(); ++j) dp[0][j] = dp[0][j - 1] + grid[0][j];
        for (int i = 1; i < grid.size(); ++i) {
            for (int j = 1; j < grid[0].size(); ++j) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[grid.size() - 1][grid[0].size() - 1];
    }
};

发表于 2022-11-10 17:45:23 回复(0)
Java
王小汪头像 王小汪
从右下角向坐上角进行分析。每个格子记录当前格子到右下角的最大和。
dp[i][j] += Math.max(dp[i + 1][j], dp[i][j + 1]); 
public int maxValue (int[][] grid) {
        // write code here
    int row = grid.length;
    int col = grid[0].length;
    for (int i = col - 2; i >= 0; i --) {
        grid[row - 1][i] += grid[row - 1][i + 1];
    }
    for (int i = row - 2; i >= 0; i --) {
        grid[i][col - 1] += grid[i + 1][col - 1];
    }
    for (int i = row - 2; i >= 0; i --) {
        for (int j = col - 2; j >= 0; j--) {
            grid[i][j] += Math.max(grid[i + 1][j], grid[i][j + 1]);
        }
    }
    return grid[0][0];
}


发表于 2022-01-05 23:54:00 回复(1)
Java
黄渡菜鸟头像 黄渡菜鸟
// 简单DP，dp[i+1] = max(dp[i], dp[i+1]) + grid[i][j]
    public int maxValue (int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int[] dp = new int[grid[0].length + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 0;
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                dp[j + 1] = Math.max(dp[j], dp[j + 1]) + grid[i][j];
            }
        }
        return dp[grid[0].length];
    }
发表于 2021-11-07 10:32:53 回复(1)
Go
法法飞头像 法法飞 
package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param grid int整型二维数组
 * @return int整型
 */
func maxValue( grid [][]int ) int {
    // write code here
    dp := make([][]int, len(grid)+1)
    for i := range dp {
        dp[i] = make([]int, len(grid[0])+1)
    }
    dp[1][1] = grid[0][0]
    for i:= range grid {
        for j := range grid[i] {
            x, y := i+1, j+1
            dp[x][y] = max(dp[x-1][y], dp[x][y-1]) + grid[i][j]
        } 
    }
    return dp[len(grid)][len(grid[0])]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b

发表于 2024-10-07 13:06:56 回复(0)
Java
牛客537133138号头像 牛客537133138号
//不修改原本数组，一维数组解决
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型二维数组
     * @return int整型
     */
    public int maxValue (int[][] grid) {
        //其实还有优化空间，只需要一维数组即可，一开始处理最上面一行，只保存一行的值，之后从第2列开始处理，第一个就是最上面的相加，第二个开始就是上面的想加还是最左边的相加，一直更新即可
        int[] dp = new int[grid[0].length];
        //处理第一个位置
        dp[0] = grid[0][0];
        //处理第一行
        for (int j = 1; j < grid[0].length; j++) {
            dp[j] = dp[j - 1] + grid[0][j];
        }
        //处理剩下的
        for (int i = 1; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (j == 0) {
                    //最左边的只能由上面下面
                    dp[j] += grid[i][j];
                } else {
                    //最左边的已经更新好，并且放在第一个，之后每次同一行上的上一个更新好的都放在了前一个，而dp当前位置上的就是上面一个位置的最优值
                    dp[j] = Math.max(dp[j - 1] + grid[i][j], dp[j] + grid[i][j]);
                }
            }
        }
        return dp[grid[0].length - 1] ;
    }
}
发表于 2024-08-04 15:38:18 回复(0)
wgahdx头像 wgahdx 
int maxValue(int** grid, int gridRowLen, int* gridColLen ) {
    // write code here
    
    int m=gridRowLen;
    int n=*gridColLen;
    //对新数组的第一行重新赋值，第一行的最大值只能来自最左边，第一个值是固定不变的
    for (int j=1; j<n; j++) {
        grid[0][j]+=grid[0][j-1];
    }
    //对数组的第一列进行重新赋值，只能来自上方
    for(int i=1;i<m;i++ )
    {
        grid[i][0]+=grid[i-1][0];
    }
    for (int i=1;i<m ; i++) {
        for (int j=1; j<n; j++) {
            //利用三目运算符
            grid[i][j]= grid[i][j-1]>grid[i-1][j]?grid[i][j]+grid[i][j-1]:grid[i][j]+grid[i-1][j];
        }
    
    }
    return grid[m-1][n-1];
}

编辑于 2024-03-28 19:41:52 回复(0)
C
牛客770548236号头像 牛客770548236号 
int maxValue(int** grid, int gridRowLen, int* gridColLen) {
    // 判断输入是否合法
    if (grid == NULL || gridRowLen <= 0 || gridColLen == NULL || *gridColLen <= 0) 
    {
        return 0;
    }
    
    int m = gridRowLen;
    int n = *gridColLen;
    
    // 创建 dp 数组并初始化第一个格子
    int dp[m][n];
    dp[0][0] = grid[0][0];
    
    // 初始化第一行
    for (int j = 1; j < n; j++) 
    {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    
    // 初始化第一列
    for (int i = 1; i < m; i++) 
    {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    
    // 计算其他格子的最大价值
    for (int i = 1; i < m; i++) 
    {
        for (int j = 1; j < n; j++) 
        {
            dp[i][j] = fmax(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    
    // 返回右下角格子的最大价值
    return dp[m-1][n-1];
}
//x++||y++

编辑于 2023-12-29 14:31:54 回复(0)
cua-cua-cua头像 cua-cua-cua
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型vector<vector<>>
     * @return int整型
     */
    int maxValue(vector<vector<int> >& grid) {
        // write code here
        int x = 0, y = 0;
        vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size()));
        dp[0][0] = grid[0][0];
        for(int i = 0;i < grid.size();i++){
            for(int j = 0;j < grid[0].size();j++){
                if(i - 1 >= 0 && j - 1 >= 0){
                    if(dp[i - 1][j] > dp[i][j - 1]){
                        dp[i][j] = grid[i][j] + dp[i - 1][j];
                    }
                    else{
                        dp[i][j] = grid[i][j] + dp[i][j - 1];
                    }
                }
                else{
                    if(i == 0 && j > 0){
                        dp[i][j] = grid[i][j] + dp[i][j - 1];
                    }
                    else if(i > 0 && j == 0){
                        dp[i][j] = grid[i][j] + dp[i - 1][j];
                    }
                }
            }
        }
        return dp[grid.size() - 1][grid[0].size() - 1];
        //贪心，局部最优
        // int x = 0;
        // int y = 0;
        // int sum = grid[0][0];
        // while(x < grid.size() || y < grid[0].size()){
        //     if(x == grid.size() - 1 && y == grid[0].size() - 1) break;
        //     if(x < grid.size() - 1 && y < grid[0].size() - 1){
        //         if(grid[x + 1][y] > grid[x][y + 1]){
        //             sum += grid[x + 1][y];
        //             x += 1;
        //         }
        //         else{
        //             sum += grid[x][y + 1];
        //             y += 1;
        //         }
        //     }
        //     if(x == grid.size() - 1 && y < grid[0].size() - 1){
        //         sum += grid[x][y + 1];
        //         y += 1;
        //     }
        //     else if(y == grid[0].size() - 1 && x < grid.size() - 1){
        //         sum += grid[x + 1][y];
        //         x += 1;
        //     }
        //     cout<<"x:"<<x<<","<<"y:"<<y<<","<<"sum:"<<sum<<endl;
        // }
        // //cout<<"sum:"<<sum<<endl;
        // return sum;
    }
};
发表于 2023-08-25 15:36:24 回复(0)
不让我进拉倒头像 不让我进拉倒 
class Solution:
    def maxValue(self , grid: List[List[int]]) -> int:
        # write code here
        # 动态规划
        m, n = len(grid), len(grid[0])
        # dp[i][j]表示到达(i, j)位置时的最大价值
        dp = [[0] * n for _ in range(m)]
        # 初始化第一行和第一列
        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] + grid[i][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j - 1] + grid[0][j]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        return dp[-1][-1]

发表于 2023-07-18 15:53:03 回复(0)
小小小孩头像 小小小孩 
int max_val(int a,int b)
{
    return a>b?a:b;
}
int maxValue(int** grid, int gridRowLen, int* gridColLen ) 
{
    // write code here
    int i=0,col = *gridColLen;
    for(i=gridRowLen-2;i>=0;i--)
        grid[i][col-1] += grid[i+1][col-1];
    for(i=col-2;i>=0;i--)
        grid[gridRowLen-1][i] += grid[gridRowLen-1][i+1];
    for(int i=gridRowLen-2;i>=0;i--)
        for(int j=col-2;j>=0;j--)
            grid[i][j] +=max_val(grid[i+1][j],grid[i][j+1]);
    return grid[0][0];
}

发表于 2023-06-12 14:17:48 回复(0)
^ǒ^月亮船^头像 ^ǒ^月亮船^ 

import java.util.*;

//二维动态规划，创建一个dp二维数组，长度比grid大一
//dp中存放对应的grid数组中走到这个位置的礼物最大价值，
//状态转移方程：
//dp[i][j] = Math.max( dp[i-1][j] + grid[i-1][j-1], dp[i][j-1] + grid[i-1][j-1])
public class Solution {
    /**
     * @param grid int整型二维数组
     * @return int整型
     */
    public int maxValue (int[][] grid) {
        // write code here
        int[][] dp = new int[grid.length + 1][grid[0].length + 1];

        //行
        for (int i = 1; i < dp.length; i++) {
            //列
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = Math.max(dp[i - 1][j] + grid[i - 1][j - 1],
                                    dp[i][j - 1] + grid[i - 1][j - 1]);
            }
        }
        return dp[dp.length - 1][dp[0].length - 1];
    }
}


发表于 2023-04-17 15:24:13 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param grid int整型二维数组 
 * @return int整型
*/
func maxValue( grid [][]int ) int {
    m,n:=len(grid),len(grid[0])
    for i:=1;i<m;i++{
        grid[i][0]+=grid[i-1][0]
    }
    for i:=1;i<n;i++{
        grid[0][i]+=grid[0][i-1]
    }
    for i:=1;i<m;i++{
        for j:=1;j<n;j++{
            grid[i][j]+=max(grid[i-1][j],grid[i][j-1])
        }
    }
    return grid[m-1][n-1]
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

发表于 2023-03-04 11:31:13 回复(0)
Python3
牛客292060878号头像 牛客292060878号 
class Solution:
    def maxValue(self , grid: List[List[int]]) -> int:
        # write code here
        # 动态规划
        m, n = len(grid), len(grid[0])
        dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1,n + 1):
                dp[i][j] = max(grid[i - 1][j - 1] + dp[i - 1][j], grid[i - 1][j - 1] + dp[i][j - 1])
        return dp[-1][-1]
动态规划，每次走最大路径即可完成
发表于 2023-02-26 18:09:10 回复(0)
Python 3
牛客116003403号头像 牛客116003403号 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param grid int整型二维数组
# @return int整型
#
class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        # write code here
        M = len(grid)
        N = len(grid[0])
        dp = [[0]*N for m in range(M)]

    # 记录当前位置的礼物的最大

        for i in range(0, len(grid)):
            for j in range(0, len(grid[0])):

            # 初始化第一行，第一列的元素，它不可能从上面，或者左边移动过来，所以说它的大小就是它最大的价值

                if i == 0 and j == 0:
                    print(grid[0][0])
                    dp[i][j] = grid[i][j]

            # 棋盘中非第一行，非第一列中的元素的最大的情况

                elif len(grid) > i > 0 and len(grid[0]) > j > 0:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

                # 棋盘的第一行只能从左移动过去，从上面移动下来不可能

                elif i-1 < 0:
                    print("行列", i, j)
                    dp[i][j] = dp[i][j-1]+grid[i][j]

                # 棋盘的第一列，不可能从左边移动过来，所以只能从上面移动过来
                elif j-1 < 0:
                    dp[i][j] = dp[i-1][j] + grid[i][j]

        return dp[M-1][N-1]

发表于 2023-02-21 15:37:12 回复(0)
加油sssssp在招手头像 加油sssssp在招手
class Solution:
    def maxValue(self , grid: List[List[int]]) -> int:
        # write code here
        rows, cols = len(grid), len(grid[0])
        dp = [[0] * cols for _ in range(rows)]
        dp[0][0] = grid[0][0]
        for i in range(1, rows):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for j in range(1, cols):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        for i in range(1, rows):
            for j in range(1, cols):
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[-1][-1]
发表于 2022-12-11 20:29:28 回复(0)
C++
李顺利plus头像 李顺利plus 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int maxValue(vector<vector<int> >& grid) {
        // write code here
        int m=grid.size();         //行数m
        int n=grid[0].size();         //列数n
        int rec[m][n];               //记录最大值的二维数组rec，这里空间复杂度高一些
        rec[0][0]=grid[0][0];     //初始化左上角rec
        for(int i=1;i<m;i++){         //填补rec的第一列
            rec[i][0]=rec[i-1][0]+grid[i][0];
        }
        for(int i=1;i<n;i++){        //填补rec的第一行
            rec[0][i]=rec[0][i-1]+grid[0][i];
        }
        for(int i=1;i<m;i++){        //找剩下的rec空的地方的最大值，遍历一遍
            for(int j=1;j<n;j++){
                rec[i][j]=max(rec[i-1][j],rec[i][j-1])+grid[i][j];
            }
        }
        return rec[m-1][n-1];
    }
};

发表于 2022-11-16 16:23:57 回复(0)
提交观点

问题信息

动态规划 数组
难度：
47条回答 5837浏览

热门推荐

通过挑战的用户

查看代码

相关试题

礼物的最大价值

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号