小東所在公司要發(fā)年終獎，而小東恰好獲得了最高福利，他要在公司年會上參與一個抽獎游戲，游戲在一個6*6的棋盤上進行，上面放著36個價值不等的禮物，每個小的棋盤上面放置著一個禮物，他需要從左上角開始游戲，每次只能向下或者向右移動一步，到達右下角停止，一路上的格子里的禮物小東都能拿到，請設(shè)計一個算法使小東拿到價值最高的禮物。

給定一個6*6的矩陣board，其中每個元素為對應(yīng)格子的禮物價值,左上角為[0,0],請返回能獲得的最大價值，保證每個禮物價值大于100小于1000。

public class Main{

    //動態(tài)規(guī)劃
    //每個點當前所能獲得的最大價值 = 上一個點所能獲得的最大價值 + 自身點的價值
    public static int getMostValue(int[][] board) {
        int n = board.length;        // 棋盤寬高 n * n
        int[][] curMostValue = new int[n][n];    // 每個點所能獲得的最大價值
        for(int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < n ; j++) {
                if(i == 0 && j == 0) // 棋盤左上角點獲得的最大價值 = 自身點的價值
                    curMostValue[i][j] = board[i][j];
                else if(i == 0) // 第一行棋盤點的價值 = 左側(cè)點的最大價值 + 自身點的價值
                    curMostValue[i][j] = curMostValue[i][j - 1] + board[i][j];
                else if(j == 0) // 第一列棋盤點的價值 = 上側(cè)點的最大價值 + 自身點的價值
                    curMostValue[i][j] = curMostValue[i - 1][j] + board[i][j];
                else // 其他棋盤點的價值 = max(左側(cè)點的最大價值, 上側(cè)點的最大價值) + 自身點的價值
                    curMostValue[i][j] = Math.max(curMostValue[i - 1][j], curMostValue[i][j - 1]) + board[i][j];
            }
        }
        return curMostValue[n - 1][n - 1]; //右下角點的curMostValue即為可拿到的最大價值
    }

    public static void main(String[] args) {
        int[][] board ={
                {2,2,1,1,2,1},
                {3,2,4,3,1,2},
                {1,2,5,4,1,3},
                {2,1,3,3,2,1},
                {1,3,2,4,1,2},
                {2,2,4,1,2,2}};
        System.out.println(getMostValue(board));
    }
}