首页 > 试题广场 >

礼物的最大价值

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

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

输出

备注:

算法知识视频讲解

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