LeetCode算法题目之如何计算礼物的最大价值

问题描述

有一个m行n列的棋盘，每个格子中放有一定数量的礼物，你从棋盘的左上角开始，只能向右或向下移动，最终到达棋盘的右下角。求在所经过的路径上，能够获得礼物的最大总价值。

解题思路

这是一个经典的动态规划问题。假设f(i, j)表示到达第i行第j列格子的最大总价值，则存在以下递推关系：

1. f(i, j) = max(f(i-1, j), f(i, j-1)) + grid(i, j)。即到达第i行第j列的最大总价值为从上方和左方路径中选择价值较大的一个，并加上当前格子中的礼物价值。
2. 由于只能向右或向下移动，因此第一行和第一列的最大总价值可以直接计算。即f(i, 0) = f(i-1, 0) + grid(i, 0)和f(0, j) = f(0, j-1) + grid(0, j)。

最终，f(m-1, n-1)即为所求的礼物的最大价值。

代码实现

def maxGiftValue(grid):
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    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[m-1][n-1]

时间复杂度分析

假设棋盘的尺寸为m行n列，则动态规划的时间复杂度为O(m*n)，其中m和n分别表示棋盘的行数和列数。因此，该算法的时间复杂度为O(m*n)。