题⽬描述
在⼀个m × n的棋盘的每⼀格都放有⼀个礼物，每个礼物都有⼀定的价值（价值⼤于 0）。你可以从棋盘的左上⻆开始拿格⼦⾥的礼物，并每次向右或者向下移动⼀格、直到到达棋盘的右下⻆。给定⼀个棋盘及其上⾯的礼物的价值，请计算你最多能拿到多少价值的礼物？
如输⼊这样的⼀个⼆维数组，
[
[1,3,1],
[1,5,1],
[4,2,1]
]那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为 12
思路及解答
这道题其实⼀看就知道是动态规划，棋盘中的每个⼩格⼦，都是和上⽅，或者左⽅的格⼦有关。既然是动态规划，那么我们先定义状态：
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 数组。
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];
}
}- 时间复杂度： O(nm) ，需要计算完⾥⾯的⼩格⼦
- 空间复杂度： O(1) ，优化后可以实现原地操作，不需要额外的空间