剑指OfferV2(增) -- 礼物的最大价值
Part0前言
剑指Offer & LeetCode刷题仓库：
https://github.com/Damaer/CodeSolution文档地址：https://damaer.github.io/CodeSolution/刷题仓库介绍：刷题仓库：CodeSolution编程知识库：https://github.com/Damaer/Coding文档地址：https://damaer.github.io/Coding/#/剑指OfferV1 系列已经完成，补增 V2 题目以及C++语言解法，欢迎关注~
Part147.礼物的最大价值
1题目描述
在一个m × n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
如输入这样的一个二维数组，
[
[1,3,1],
[1,5,1],
[4,2,1]
]
那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为12
示例1
输入：[[1,3,1],[1,5,1],[4,2,1]]
返回值：12
2思路 & 解答
这道题其实一看就知道是动态规划，棋盘中的每个小格子，都是和上方，或者左方的格子有关。既然是动态规划，那么我们先定义状态：
dp[i][j]]: 从（0，0）到（i，j）所能拿到的礼物的最大价值
定义好状态之后，需要找出状态转移方程，也就是如何从前面的结果中，推导到现在的结果，在这道题中，只能向右或者向下，那么假设当前格子的礼物是gift[i][j]，当前的最大价值dp[i][j]是Max(dp[i-1][j]+gift[i][j],dp[i][j-1]+gift[i][j])。
当然如果是第一行和第一列，其实是边界情况，不需要处理，dp[i][j] = gift[i][j]
总结一下：
但是我们可以直接在原数组上操作，不用新建dp数组。Java代码实现如下：
public class Solution47 {
public int maxValue(int[][] gifts) {
int n = gifts.length, m = gifts[0].length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int x = gifts[i][j];
if (i - 1 >= 0) {
gifts[i][j] = Math.max(gifts[i][j], x + gifts[i - 1][j]);
}
if (j - 1 >= 0) {
gifts[i][j] = Math.max(gifts[i][j], x + gifts[i][j - 1]);
}
}
}
return gifts[n - 1][m - 1];
}
}
c++代码如下：
class Solution {
public:
int maxValue(vector<vector<int> >& gifts) {
int n = gifts.size(), m = gifts[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int x = gifts[i][j];
if (i - 1 >= 0) {
gifts[i][j] = max(gifts[i][j], x + gifts[i - 1][j]);
}
if (j - 1 >= 0) {
gifts[i][j] = max(gifts[i][j], x + gifts[i][j - 1]);
}
}
}
return gifts[n - 1][m - 1];
}
};
- 时间复杂度：
O(nm)，需要计算完里面的小格子 - 空间复杂度：
O(1)，优化后可以实现原地操作，不需要额外的空间
【作者简介】
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，Redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。
平日时间宝贵，只能使用晚上以及周末时间学习写作
腾讯云开发者
