当前位置 博文首页 > 数据结构和算法：剑指 Offer-动态规划解礼物的最大价值
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
这题可以参照409，动态规划求不同路径，第409题让求的是有多少种路径，而这题让求的是所有路径中数字和最大的值。这题很容易想到的解决方式就是动态规划。
public int maxValue(int[][] grid) {
//边界条件判断
if (grid == null || grid.length == 0)
return 0;
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
//初始化dp的最上面一行，从左到右累加
for (int i = 1; i < n; i++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
//初始化dp的最左边一列，从上到下累加
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
//下面是递推公式的计算
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
为了方便计算我们还可以把dp的宽和高增加1，也就是dp的最上面一行和最左边一列不存储任何数值，他们都是0，这样是为了减少一些判断
public int maxValue(int[][] grid) {
if (grid == null || grid.length == 0)
return 0;
int m = grid.length;
int n = grid[0].length;
//为了方便计算，dp的宽和高都增加了1
int[][] dp = new int[m + 1][n+1];
//下面是递推公式的计算
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
}
}
return dp[m][n];
}
public int maxValue(int[][] grid) {
if (grid == null || grid.length == 0)
return 0;
int m = grid.length;
int n = grid[0].length;
//数组改成一维的
int[] dp = new int[n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[j + 1] = Math.max(dp[j], dp[j + 1]) + grid[i][j];
}
}
return dp[n];
}
我们再来仔细看这道题，题中没说不可以修改原来数组的值，所以我还可以使用题中的二维数组来代替二维dp数组
public int maxValue(int[][] grid) {
//边界条件判断
if (grid == null || grid.length == 0)
return 0;
int m = grid.length;
int n = grid[0].length;
//初始化dp的最上面一行，从左到右累加
for (int i = 1; i < n; i++) {
grid[0][i] += grid[0][i - 1];
}
//初始化dp的最左边一列，从上到下累加
for (int i = 1; i < m; i++) {
grid[i][0] += grid[i - 1][0];
}
//下面是递推公式的计算
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
grid[i][j] = Math.max(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
}
}
return grid[m - 1][n - 1];
}
这样最终我们把空间复杂度从O(MN)降到O(1)。
cs