当前位置：首页 > news >正文

【LeetCode】剑指 Offer（24）

news 2025/8/23 4:46:00

题目：剑指 Offer 47. 礼物的最大价值 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

题目：剑指 Offer 47. 礼物的最大价值 - 力扣（Leetcode）

题目的接口：

class Solution {
public:int maxValue(vector<vector<int>>& grid) {}
};

解题思路：

这是一道动态规划的题目，

具体思路如下：

我们将这个问题分解成一个个小问题：

看一下这个例子：

如果第一行的2是终点，那么他的最大路径是dp[0][0] + dp[0][1]；

如果第二行的1是终点，那么他的最大路径是dp[1][0] + dp[0][0]；

然后，

我们将这两个位置的数值，改成dp[0][0] + dp[0][1]、dp[1][0] + dp[0][0]，

如下图：

那么以此类推：

如果dp[0][2]是终点，dp[0][2]就等于 dp[0][1] + dp[0][2]；

如果dp[2][0]是终点，dp[2][0]就等于 dp[1][0] + dp[2][0];

如果dp[1][1]是终点，dp[1][1]就等于 max(dp[0][1], dp[1][0]) + dp[1][1]。

按照这个规律走，最后，右下角的那个就是最大路径的值。

这就是将一个大的问题，拆解成一个个小问题解决。

代码：

class Solution {
public:int maxValue(vector<vector<int>>& grid) {//这是棋盘的行和列int row = grid.size();int col = grid[0].size();//这是棋盘第一行每一格的路径的最大值计算for(int i = 1; i < col; i++){grid[0][i] = grid[0][i - 1] + grid[0][i];}//这是棋盘第一列每一格的路径的最大值计算for(int i = 1; i < row; i++){grid[i][0] = grid[i - 1][0] + grid[i][0];}//这是棋盘剩余位置的每一格作为终点的路径最大值计算for(int i = 1; i < row; i++){for(int j = 1; j < col; j++){grid[i][j] = max(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];}}//最后返回右下角的路径最大值return grid[row - 1][col - 1];}
};