題目：在一個m×n的棋盤的每一格都放有一個禮物，每個禮物都有一定的價值（價值大于0）搏嗡。你可以從棋盤的左上角開始拿格子里的禮物之剧，并每次向右或者向下移動一格得问，直到到達棋盤的右下角。給定一個棋盤及其上面的禮物丈氓，請計算你最多能拿到多少價值的禮物周循？
例如，在下面的棋盤中万俗，如果沿著加粗的數(shù)字的線路（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)公条。
優(yōu)化之后的代碼
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)迂曲。
