剑指Offer第47题——礼物的最大价值

在一个mxn的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（大于0）从棋盘的左上角开始，每次可以往右边或者下边移动一格，知道到达棋盘的右下角。给定一个棋盘和上面的礼物，计算我们最多可以拿到多少价值的礼物

典型的动态规划问题，动态规划常常适用于有重叠子问题和最优子结构性质的问题。
到达处有两种情况：

1. 从左边来
   即
2. 从上边来
   即

求到终点能拿到的价值的最大值，即为求每一个子问题的最大值，即为到达每一个格子所拿到的礼物的值都是最大的，即取
可以发现，要知道当前格子能获得最大礼物价值，需要用到当前格子左边一个和上面一个格子的最大礼物价值和

public int getMaxVal(int[] gifts, int rows, int cols) {
        if (gifts == null || gifts.length == 0)
            return 0;
        int[][] maxVal = new int[rows][cols];
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                int left = 0;
                int up = 0;
                if (row > 0) {
                    up = maxVal[row - 1][col];
                }
                if (col > 0) {
                    left = maxVal[row][col - 1];
                }
                maxVal[row][col] = Math.max(up, left) + gifts[row * col + col];
            }
        }
        return maxVal[rows - 1][cols - 1];
    }