首页 > 试题广场 >

礼物的最大价值

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

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

输出

备注:

算法知识视频讲解

Python3

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