本系列導(dǎo)航：劍指offer（第二版）java實(shí)現(xiàn)導(dǎo)航帖
面試題47：禮物的最大值
題目要求：
在一個(gè)m*n的棋盤的每一個(gè)格都放有一個(gè)禮物，每個(gè)禮物都有一定價(jià)值（大于0）。從左上角開始拿禮物奖地，每次向右或向下移動(dòng)一格，直到右下角結(jié)束赋焕。給定一個(gè)棋盤参歹，求拿到禮物的最大價(jià)值。例如隆判，對于如下棋盤
1 10 3 8
12 2 9 6
5 7 4 11
3 7 16 5
禮物的最大價(jià)值為1+12+5+7+7+16+5=53犬庇。
解題思路：
思路1：動(dòng)態(tài)規(guī)劃
申請一個(gè)與原矩陣行列數(shù)一樣的二維數(shù)組dp[][]，初始化dp[0][i] = data[0][i]蜜氨；然后依次更新dp的每一行即可械筛。由于第m行的值與第m-1行和第m行有關(guān)，因此可以對dp進(jìn)行簡化飒炎，僅用兩行的dp埋哟，即dp[2][]即可完成狀態(tài)的記錄與更新。
思路2：廣度優(yōu)先遍歷
這個(gè)棋盤其實(shí)可以看成一個(gè)有向圖郎汪，起點(diǎn)為左上角赤赊，終點(diǎn)為右下角，每一點(diǎn)僅僅指向右側(cè)和下側(cè)煞赢。因此我們可以從左上角開始進(jìn)行廣度優(yōu)先遍歷抛计。此外，遍歷過程中可以進(jìn)行剪枝照筑，最終移動(dòng)到右下角時(shí)會(huì)僅剩下一個(gè)枝吹截，該路徑所經(jīng)的點(diǎn)的數(shù)值之和即為所求瘦陈。
package chapter5;
import java.util.LinkedList;
import java.util.Queue;
/**
* Created with IntelliJ IDEA
* Author: ryder
* Date : 2017/8/11
* Time : 13:03
* Description:禮物的最大價(jià)值
**/
public class P233_MaxValueOfGifts {
//方法一：動(dòng)態(tài)規(guī)劃
public static int getMaxVaule(int[][] data){
if(data.length==0||data[0].length==0)
return 0;
int[][] dp = new int[2][data[0].length];
int dpCurRowIndex = 0,dpPreRowIndex = 0;
for(int row=0;row<data.length;row++){
dpCurRowIndex = row&1;
dpPreRowIndex = 1 - dpCurRowIndex;
for(int col=0;col<data[0].length;col++){
if(col==0)
dp[dpCurRowIndex][col] = dp[dpPreRowIndex][col]+data[row][col];
else{
if(dp[dpPreRowIndex][col]>=dp[dpCurRowIndex][col-1])
dp[dpCurRowIndex][col] = dp[dpPreRowIndex][col]+data[row][col];
else
dp[dpCurRowIndex][col] = dp[dpCurRowIndex][col-1]+data[row][col];
}
}
}
return dp[(data.length-1)&1][data[0].length-1];
}
//方法二：有向圖的遍歷（廣度優(yōu)先，可再剪枝進(jìn)行優(yōu)化）
public static int getMaxVaule2(int[][] data){
if(data.length==0||data[0].length==0)
return 0;
int maxRowIndex = data.length-1;
int maxColIndex = data[0].length-1;
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(0,0,data[0][0]));
Node nodeCur = null;
while (!(queue.peek().row==maxRowIndex && queue.peek().col==maxColIndex)){
nodeCur = queue.poll();
if(nodeCur.row!=maxRowIndex)
queue.offer(new Node(nodeCur.row+1,nodeCur.col,nodeCur.sum+data[nodeCur.row+1][nodeCur.col]));
if(nodeCur.col!=maxColIndex)
queue.offer(new Node(nodeCur.row,nodeCur.col+1,nodeCur.sum+data[nodeCur.row][nodeCur.col+1]));
}
int maxSum = 0,temp = 0;
while (!queue.isEmpty()){
temp = queue.poll().sum;
if(temp>maxSum)
maxSum = temp;
}
return maxSum;
}
public static class Node{
int row;
int col;
int sum;
public Node(int r,int c,int s){
row = r;col = c;sum = s;
}
}
public static void main(String[] args){
int[][] data = {
{1,10,3,8},
{12,2,9,6},
{5,7,4,11},
{3,7,16,5}};
System.out.println(getMaxVaule(data));
System.out.println(getMaxVaule2(data));
}
}
運(yùn)行結(jié)果
53
53
