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

2021/12/3 6:06:29

本文主要是介绍力扣 - 剑指 Offer 47. 礼物的最大价值,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

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

思路1

  • 因为是要求最大价值,而且只能移动下方或者右方,因此,每个位置的最大值就是本身的值加上上边 / 左边 中的最大值,然后每次遍历都可以复用上一次的值。因此我们可以得到状态转移方程:
    • $ dp[i][j]=\begin{matrix} max(dp[i-1][j], dp[i][j-1]) + grid[i][j] \end{matrix} $
  • 我们可以创建一个行和列都要多一行的 dp 数组,这样子可以不用判断条件了,但是同时也要注意 grid 中的坐标都要减去 1,因为我们是从 1 开始的:

代码

class Solution {
    public int maxValue(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        // 创建dp数组,让 row 和 col 都多创建一行就可以避免判断边界值问题
        int dp[][] = new int[row+1][col+1];

        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                // 这里的 grid 中 i-1 和 j-1 是因为我们是从 1 开始的,所以要减去 1 才是原始正确的位置
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
            }
        }

        // 最后直接返回数组右下角值即可
        return dp[row][col];
    }
}

复杂度分析

  • 时间复杂度:\(O(MN)\),
  • 空间复杂度:\(O(MN)\),创建 dp 数组所花费的空间

思路2

  • 然后我们可以优化一下,因为只能左走或者右走,因此第一行和第一列是固定的一条路,我们可以事先初始化计算一下第一行和第一列,到时就不用计算了。因此直接在原数组上直接进行就可以了

代码

class Solution {
    public int maxValue(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;

        // 先初始化边界
        for (int i = 1; i < row; i++) {
            grid[i][0] += grid[i-1][0];
        }
        for (int i = 1; i < col; i++) {
            grid[0][i] += grid[0][i-1];
        }

        // 遍历
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                // 选择左边或者上边
                grid[i][j] += Math.max(grid[i-1][j], grid[i][j-1]);
            }
        }

        // 最后直接返回数组右下角值即可
        return grid[row-1][col-1];
    }
}

复杂度分析

  • 时间复杂度:\(O(MN)\),
  • 空间复杂度:\(O(1)\),无需创建 dp 数组


这篇关于力扣 - 剑指 Offer 47. 礼物的最大价值的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程