礼物的最大价值

问题陈述

在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?

示例:

1
2
3
4
5
6
7
8
输入: 
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

思路分析

可使用动态规划解决此题。

状态定义:设动态规划矩阵dp,dp[i,j]代表从棋盘的左上角开始,到达[i,j]单元格能拿到最多礼物的累积值。

转移方程

  1. 当i=0,j=0时,为起始元素。

  2. 当i=0,j$\ne$0时,为矩阵第一行元素,只可能从左边到达。

  3. 当i$\ne$0,j=0时,为矩阵第一列元素,只可能从上边到达。

  4. i0i\ne0,j0j\ne0时,可从左边或上边到达,据题意取两者中的最大值

初始状态:dp[0][0]=grid[0][0]。

返回值:dp[m-1][n-1],其中m,n为矩阵的长宽,即返回dp右下角元素。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int maxValue(int[][] grid) {
int m=grid.length;
int n=grid[0].length;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==0&&j==0) continue;
else if(i==0) grid[i][j]+=grid[i][j-1];
else if(j==0) grid[i][j]+=grid[i-1][j];
else grid[i][j]+=Math.max(grid[i-1][j],grid[i][j-1]);
}
}
return grid[m-1][n-1];

}
}