第 47 题：礼物的最大价值
传送门：礼物的最大价值，牛客网 online judge 地址。
在一个 m×n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。
你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格直到到达棋盘的右下角。
给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？
注意：
m,n>0样例：
输入：
[ [2,3,1], [1,7,1], [4,6,1] ]输出：19
解释：沿着路径
2→3→7→6→1可以得到拿到最大价值礼物。
思路：动态规划。礼物要么来自左边一格，要么来自上面一格，两者取最大。要特殊判断的就是边界情况。另外可以使用一维数组完成动态规划。如果可以修改 grid，直接在 grid 上修改就可以了，不用辅助空间。
- 动态规划。
- 可以尽量减少空间复杂度。
Python 代码：
class Solution(object):
def getMaxValue(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m = len(grid)
if m == 0:
return 0
n = len(grid[0])
dp = [None for _ in range(n)]
dp[0] = grid[0][0]
for i in range(1, n):
dp[i] = dp[i - 1] + grid[0][i]
for i in range(1, m):
for j in range(n):
if j == 0:
dp[j] += grid[i][0]
else:
dp[j] = grid[i][j] + max(dp[j - 1], dp[j])
return dp[n - 1]
Java 代码：
public class Solution {
public int getMaxValue(int[][] matrix) {
int row = matrix.length;
if (row == 0) {
return 0;
}
int col = matrix[0].length;
int[][] dp = new int[row][col];
dp[0][0] = matrix[0][0];
for (int j = 1; j < col; j++) {
dp[0][j] = dp[0][j - 1] + matrix[0][j];
}
for (int i = 1; i < row; i++) {
dp[i][0] = dp[i - 1][0] + matrix[i][0];
for (int j = 1; j < col; j++) {
dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
}
}
return dp[row - 1][col - 1];
}
public static void main(String[] args) {
int[][] matrix = new int[][]{
{1, 10, 3, 8},
{12, 2, 9, 6},
{5, 7, 4, 11},
{3, 7, 16, 5}
};
Solution solution = new Solution();
int maxValue = solution.getMaxValue(matrix);
System.out.println(maxValue);
}
}
Java 代码：
public class Solution2 {
public int getMaxValue(int[][] matrix) {
int row = matrix.length;
if (row == 0) {
return 0;
}
int col = matrix[0].length;
int[] dp = new int[col];
dp[0] = matrix[0][0];
for (int j = 1; j < col; j++) {
dp[j] = dp[j - 1] + matrix[0][j];
}
for (int i = 1; i < row; i++) {
dp[0] = dp[0] + matrix[i][0];
for (int j = 1; j < col; j++) {
dp[j] = Integer.max(dp[j], dp[j - 1]) + matrix[i][j];
}
}
return dp[col - 1];
}
public static void main(String[] args) {
int[][] matrix = new int[][]{
{1, 10, 3, 8},
{12, 2, 9, 6},
{5, 7, 4, 11},
{3, 7, 16, 5}
};
Solution2 solution2 = new Solution2();
int maxValue = solution2.getMaxValue(matrix);
System.out.println(maxValue);
}
}
Java 代码：
public class Solution3 {
public int getMaxValue(int[][] matrix) {
int row = matrix.length;
if (row == 0) {
return 0;
}
int col = matrix[0].length;
int[] dp = new int[col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
dp[j] = Integer.max(dp[j], j - 1 < 0 ? 0 : dp[j - 1]) + matrix[i][j];
}
}
return dp[col - 1];
}
public static void main(String[] args) {
int[][] matrix = new int[][]{
{1, 10, 3, 8},
{12, 2, 9, 6},
{5, 7, 4, 11},
{3, 7, 16, 5}
};
Solution3 solution3 = new Solution3();
int maxValue = solution3.getMaxValue(matrix);
System.out.println(maxValue);
}
}
