LeetCode - 剑指 Offer 47. 礼物的最大价值
题目描述
难度：中等
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示：
0 < grid.length <= 200
0 < grid[0].length <= 200
分析
本题利用动态规划解题；先分析题目，题目要求得出从左上角开始走，那条路线走到右下角时，礼物价值最大，并且只能是向右移动和向左移动；
可以定义状态 dp(i,j) 是 走到第 i 行 第 j 列时该路线的最大礼物价值；
由于行进路线确定只能是向右或者向下，则必然是从 (i - 1,j) 或者 (i,j - 1)到达 (i,j) 这个礼物;
由于要取最大礼物价值 则有状态转移方程 dp (i,j) = max(dp(i - 1,j), dp(i,j - 1)) + value[i][j]
我们还可以初始化第一行和第一列的值，因为这两条路线上获取礼物的路线是一致的，第一行也就是 dp (0,j) 的礼物只能由 dp(0,j-1) + values[0][j]获取，因为 i 已经是最小值了，不存在 i - 1 了，就可以略去状态转移方程中的另一个公式；第一列也是同理，只能由 dp(i - 1,0) + values[i][0]获取；
代码
public int maxValue(int[][] grid) {
int n = grid.length, m = grid[0].length;
for (int i = 1; i < n; i++){ // 初始化第一列
grid[i][0] += grid[i-1][0];
}
for (int i = 1; i < m; i++){ // 初始化第一行
grid[0][i] += grid[0][i-1];
}
for(int i = 1; i < n; i++){
for (int j = 1; j < m; j++){
grid[i][j] = Math.max(grid[i][j - 1],grid[i - 1][j]) + grid[i][j];
}
}
return grid[n-1][m - 1];
}
总结
动态规划是一个很抽象的东西，定义状态和确定状态转移方程都是比较难的东西，需要多练习，再接再厉！
岁月悠悠，衰微只及肌肤；热忱抛却，颓废必致灵魂