在一个mxn的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（大于0）从棋盘的左上角开始，每次可以往右边或者下边移动一格，知道到达棋盘的右下角。给定一个棋盘和上面的礼物，计算我们最多可以拿到多少价值的礼物
典型的动态规划问题，动态规划常常适用于有重叠子问题和最优子结构性质的问题。
到达处有两种情况：
- 从左边来
即 - 从上边来
即
求到终点能拿到的价值的最大值，即为求每一个子问题的最大值，即为到达每一个格子所拿到的礼物的值都是最大的，即取
可以发现，要知道当前格子能获得最大礼物价值，需要用到当前格子左边一个和上面一个格子的最大礼物价值和
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];
}
