侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

47 礼物的最大价值

Lin2J
2021-07-21 / 0 评论 / 0 点赞 / 177 阅读 / 1,434 字 / 正在检测是否收录...

剑指 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)$ 的价值决定的。可以得到以下的递推关系:

$$ G(i, j) = Max\{G(i-1, j), G(i, j-1)\} + g(i,j) $$

动态规划解析

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

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

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

$$ dp[i][j] = Max\{dp[i-1][j], dp[i][j-1]\} + grid[i][j] $$
  • 返回值: 返回 $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)$ 的额外空间。
0

评论区