题目描述
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例：
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示：
0 < grid.length <= 200
0 < grid[0].length <= 200
题目分析
我记得在大一时OJ上有一道类似的题目，当时是讲到了递归，然后当时能做出这道题的人都是大牛了，但是随着课程的推进和知识面的拓宽，解决这道题也有了多种方案，在这里我就介绍一下递归解法和动态规划解法，其实两者的思想都是差不多的
- 递归解法
因为只能往右走或者往下走，所以在每一个位置都只有两种情况，一是往右走，二是往下走，而最优解肯定在两者之间，所以对于一个位置而言，获得的礼物的最大价值等于Max(往右走之后能获得的最大价值，往下走之后能得到的最大价值) + 当前价值；于是，不难得出下面的代码（画成图其实就是二叉树，叶子节点的个数就是从左上方到右下方的总的路径数）：
public int slowMaxValue(int[][] grid) {
return Math.max(slowGetValue(grid, 0, 1), slowGetValue(grid, 1, 0)) + grid[0][0];
}
public int slowGetValue(int[][] grid, int x, int y) {
//越界处理
if (x == grid[0].length)
return 0;
//越界处理
if (y == grid.length)
return 0;
return Math.max(slowGetValue(grid, x + 1, y), slowGetValue(grid, x, y + 1)) + grid[x][y];
}
对于[0][1]和[1][0]两点来说，求它们能取得的最大价值都需要求[1][1]这一点的最大值，这就造成了重复的计算，消耗了大量的时间，所以这个做法在LeetCode上面直接是时间超限了；为了达到避免重复计算的目的，下面介绍一下动态规划解法。
-
动态规划解法
对于[0][1]这个点，它只能从[0][0]这点往右走；所以[0][1]能取得的最大值为[0][0]+[0][1]
对于[1][0]这个点，它只能从[0][0]这点往下走；所以[1][0]能取得的最大值为[0][0]+[1][0]
对于[1][1]这个点，它能从[0][1]这点往下走，或者从[1][0]往右走；所以[1][1]能取得的最大值为MAX([0][1],[1][0]) + [1][1]
......
对于[i][j]这个点，它能从[i-1][j]这点往下走，或者从[i][j-1]往右走；所以[i][j]能取得的最大值为MAX([i-1][j],[i][j-1]) + [i][j]
不难推出状态转移方程：
getValue [ i ] [ j ] = MAX( getValue [i -1] [ j ], getValue [ i ] [ j- 1] ) + value [ i ] [ j ]
过程如下图所示：
于是动手开干，代码如下：
public int maxValue(int[][] grid) {
for (int i = 1; i < grid[0].length; i++)
grid[0][i] += grid[0][i - 1];
for (int i = 1; i < grid.length; i++) {
grid[i][0] += grid[i - 1][0];
}
for (int i = 1; i < grid.length; i++) {
for (int j = 1; j < grid[0].length; j++)
grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
}
return grid[grid.length - 1][grid[0].length - 1];
}
网友评论