题目：在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？
例如，在下面的棋盘中，如果沿着加粗的数字的线路（1、12、5、7、7、16、5），那么我们能拿到最大价值为53的礼物。
1 10 3 8
12 2 9 6
5 7 4 11
3 7 16 5
练习地址
https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
参考答案
public int getMaxValueSolution1(int[][] values) {
if (values == null || values.length == 0) {
return 0;
}
int[][] maxValues = new int[values.length][values[0].length];
for (int i = 0; i < values.length; i++) {
for (int j = 0; j < values[i].length; j++) {
int left = 0, top = 0;
if (i > 0) {
top = maxValues[i - 1][j];
}
if (j > 0) {
left = maxValues[i][j - 1];
}
maxValues[i][j] = Math.max(left, top) + values[i][j];
}
}
return maxValues[maxValues.length - 1][maxValues[0].length - 1];
}
复杂度分析
- 时间复杂度：O(mn)。
- 空间复杂度：O(mn)。
优化之后的代码
public int getMaxValueSolution2(int[][] values) {
if (values == null || values.length == 0) {
return 0;
}
int[] maxValues = new int[values[0].length];
for (int i = 0; i < values.length; i++) {
for (int j = 0; j < values[i].length; j++) {
int left = 0, top = 0;
if (i > 0) {
top = maxValues[j];
}
if (j > 0) {
left = maxValues[j - 1];
}
maxValues[j] = Math.max(left, top) + values[i][j];
}
}
return maxValues[maxValues.length - 1];
}
复杂度分析
- 时间复杂度：O(mn)。
- 空间复杂度：O(n)。
