【LeetCode】剑指 Offer（24）

目录

题目：剑指 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];}
};

过啦！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。