47 礼物的最大价值

剑指 Offer 47. 礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

解题思路：

可以使用动态规划来解决。

题目说从左上角开始拿礼物，每次只能向下或者向右移动一格，一直拿到右下角，要求到右下角时拿到的礼物的价值最大。

设 $G(i, j)$ 表示从左上角经过向下或者向右走到单元格 $(i, j)$ 的礼物最大价值。 $(i, j)$ 的价值是 $g(i, j)$

显然，$G(i,j)$ 的价值是由上一个单元格（ $G(i, j-1)$ 或者 $G(i-1, j)$ 的较大者）的最大价值加上当前单元格 $(i, j)$ 的价值决定的。可以得到以下的递推关系：

动态规划解析

• 状态定义： 设动态规划矩阵 $dp$，$dp(i, j)$ 表示由棋盘的左上角开始，到达单元格 $(i, j)$ 的最大价值。

• 初始状态： 为了代码的简洁性，$dp[0][j]$ 和 $dp[i][0]$ 统一规定为 $0$ ，方便后面计算。否则需要考虑边界条件，多加几个判断。

• 转移方程：$i$ 和 $j$ 均从 $1$ 开始算起

• 返回值： 返回 $dp[m][n]$，$m$ 和 $n$ 分别为矩阵的行高和列宽，即返回 $dp$ 矩阵的右下角元素。

当然也可以直接将原二维数组作为 $dp$ 矩阵来算，只是这样会改变数组原先的数据。

代码：

public int maxValue(int[][] grid) {
    int row = grid.length;
    int col = grid[0].length;
    int[][] dp = new int[row + 1][col + 1];
    for (int x = 1; x <= row; x++) {
        for (int y = 1; y <= col; y++) {
            dp[x][y] = Math.max(dp[x - 1][y], dp[x][y - 1]) + grid[x - 1][y - 1];
        }
    }
    return dp[row][col];
}

复杂度分析

• 时间复杂度$O(MN)$：$M$，$N$ 分别为矩阵行高、列宽；动态规划需要遍历整个 $grid$ 矩阵，使用 $O(MN)$ 时间。
• 空间复杂度$O(MN)$：$dp$ 矩阵需要 $O(MN)$ 的额外空间。