首页 > 试题广场 >

礼物的最大价值

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

热度指数：30603 时间限制：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]]

输出

备注:

算法知识视频讲解

Java

牛客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)

Java

合肥吴彦祖

public int maxValue (int[][] grid) {
        // write code here
        int row = grid.length, col = grid[0].length;
        
        for(int i = 1; i < grid.length; ++i) {
            grid[i][0] += grid[i-1][0];
        }
        for(int j = 1; j < col; ++j) {
            grid[0][j] += grid[0][j-1];
        }
        
        for(int i = 1; i < row; ++i){
            for(int j = 1; j < col; ++j) {
                grid[i][j] += Math.max(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[row-1][col-1];
    }

发表于 2022-09-03 13:57:49 回复(0)

Java

GolinYoung

我觉得我这种方法和官方题解第三种差不多呀，为啥我的会超时

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型二维数组 
     * @return int整型
     */
    private int dp(int[][] grid,int i,int j){
        if(i==0&&j==0){
            return grid[0][0];
        } 
        if(i==0){
            return dp(grid,i,j-1)+grid[i][j];
        } 
        if(j==0){
            return dp(grid,i-1,j)+grid[i][j];
        }
        return Math.max(dp(grid,i-1,j),dp(grid,i,j-1))+grid[i][j];
        
            
        
    }
    public int maxValue (int[][] grid) {
        // write code here
        return dp(grid,grid.length-1,grid[0].length-1);
            
        }
    }

发表于 2022-07-28 21:14:52 回复(1)

Java

NorthXwind

    public int maxValue (int[][] grid) {
        // write code here
        int m = grid.length;
        int 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];

    }
}

发表于 2022-06-13 14:43:13 回复(0)

Java

必进大厂的飞

    /**
     * 礼物的最大价值 右下角点的最大价值为到达他所有可能路径的最大值 左边和上边
     * 状态：数组的坐标
     * 选择：怎么走 右还是下
     * 状态转移方程： dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + grid[i][j]
     * base case: dp[0][0] = grid[0][0]
     * @param grid
     * @return
     */
    public int maxValue (int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        // 自作向右自上而下
        dp[0][0] = grid[0][0];
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(i == 0 && j == 0) dp[i][j] = dp[0][0];
                else if(i - 1 < 0) dp[i][j] = dp[i][j - 1] + grid[i][j];
                else if(j - 1 < 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[grid.length - 1][grid[0].length - 1];
    }

发表于 2022-05-02 11:45:35 回复(0)

Java

624huiguorou

常见的二维dp

public class Solution {
    public int maxValue (int[][] grid) {
        int row = grid.length, column = grid[0].length;
        int[][] dp = new int[row][column];
        dp[0][0] = grid[0][0];
        //初始化第一行和第一列（dp方程里有i-1和j-1，边界到第一行和第一列）
        for(int j = 1; j < column; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
        for(int i = 1; i < row; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
        for(int i = 1; i < row; i++){
            for(int j = 1; j < column; j++){
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[row-1][column-1];
    }
}

发表于 2022-04-03 16:15:30 回复(1)

Java

ggwmz

    public int maxValue (int[][] grid) {
        /**
         * @param grid
         * @return int
         * @description 二维数组中左上角->右下角,
         * @direction 右,下
         * @target maxValue
         * @state transition equation: dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + grid[i][j]
         */
        int m = grid.length,n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0 && j==0){
                    dp[i][j] = grid[0][0];
                }else if(i==0 && j!=0){
                    dp[i][j] = dp[0][j-1] + grid[0][j];
                }else if(i!=0 && j==0){
                    dp[i][j] = dp[i][j-1];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + grid[i][j];
                }
            }
        }
        return dp[m-1][n-1];
    }


我这个哪里有问题啊，为啥没全部通过啊

发表于 2022-03-25 17:15:15 回复(1)

Java

fuuuuuck

import java.util.*;


public class Solution {
    public int maxValue (int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // 上边界赋值
        for (int i = 1; i < n; i++) {
            grid[0][i] = grid[0][i] + grid[0][i - 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] += Math.max(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }
}

发表于 2022-03-23 22:23:14 回复(0)

Java

牛客989812257号

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

发表于 2022-02-14 21:39:32 回复(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)

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

浮鸟(BAT实习ing，目标外企~)

    public int maxValue (int[][] grid) {
        
        int maxRow = grid.length;
        int maxCol = grid[0].length;
        // 创建递推矩阵：
        for(int i=0;i<maxRow;i++){
            for(int j=0;j<maxCol;j++){
                // 排除原点
                if(i==0 && j==0){
                    continue;
                }
                // 对于上边界和左边界上的值，当前值 = 当前值+之前所有值的和
                else if(i==0){
                    grid[i][j] += grid[i][j-1];
                }else if(j==0){
                    grid[i][j] += grid[i-1][j];
                }
                // 对于其他位置的值，当前值 = 当前值+max(上边值，左边值)
                else {
                    grid[i][j] += Math.max(grid[i][j-1],grid[i-1][j]);
                }
            }
        }
        return grid[maxRow-1][maxCol-1];
    }

发表于 2022-01-03 19:08:59 回复(0)

Java

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

程序猿菜菜

import java.util.*;

public class Solution {
public int maxValue (int[][] grid) {
if(grid == null || grid!=null&& grid.length ==0) return 0;
int m = grid.length;
int n= grid[0].length;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i == 0&& j == 0)continue;//i=0,j=0,起始位子
if(i == 0){//i=0,j!=0,只可从左边到达
grid[i][j]+=grid[i][j-1];
}
else if(j == 0){//i!=0,j=0,只可从上边到达
grid[i][j]+=grid[i-1][j];
}
else if(i!=0&& j!=0){//i!=0,j!=0，可从左边和上边到达，两者选大的累加
grid[i][j]+=Math.max(grid[i][j-1],grid[i-1][j]);
}
}

}
return grid[m-1][n-1];
}
}

发表于 2021-11-18 22:13:00 回复(0)

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)