题目描述
在一个m*n的棋盘的每一个格都放有一个礼物,每个礼物都有一定价值(大于0)。从左上角开始拿礼物,每次向右或向下移动一格,直到右下角结束。给定一个棋盘,求拿到礼物的最大价值。例如,对于如下棋盘
1 10 3 8
12 2 9 6
5 7 4 11
3 7 16 5
礼物的最大价值为1+12+5+7+7+16+5=53。
solution
public int getMaxPathValue(int[][] nums){
int rows = nums.length;
int cols = nums[0].length;
int[][] maxValue = new int[rows][cols];
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
int fromtop = 0;
int fromleft = 0;
if(i == 0)
fromtop = 0;
else
fromtop = maxValue[i-1][j];
if(j == 0)
fromleft = 0;
else
fromleft = maxValue[i][j-1];
maxValue[i][j] = Math.max(fromtop,fromleft) + nums[i][j];
}
}
return maxValue[rows-1][cols-1];
}
参考剑指offer第二版
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)