剑指offer第二版-47.礼物的最大值（动态规划，广度优先遍历

本系列导航：剑指offer（第二版）java实现导航帖

面试题47：礼物的最大值

题目要求：
在一个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。

解题思路：
思路1：动态规划
申请一个与原矩阵行列数一样的二维数组dp[][]，初始化dp[0][i] = data[0][i]；然后依次更新dp的每一行即可。由于第m行的值与第m-1行和第m行有关，因此可以对dp进行简化，仅用两行的dp，即dp[2][]即可完成状态的记录与更新。

思路2：广度优先遍历
这个棋盘其实可以看成一个有向图，起点为左上角，终点为右下角，每一点仅仅指向右侧和下侧。因此我们可以从左上角开始进行广度优先遍历。此外，遍历过程中可以进行剪枝，最终移动到右下角时会仅剩下一个枝，该路径所经的点的数值之和即为所求。

package chapter5;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA
 * Author: ryder
 * Date  : 2017/8/11
 * Time  : 13:03
 * Description:礼物的最大价值
 **/
public class P233_MaxValueOfGifts {
    //方法一：动态规划
    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];
    }

    //方法二：有向图的遍历（广度优先，可再剪枝进行优化）
    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));
    }
}

运行结果

53
53