面试题47(剑指offer)--礼物的最大值

题目： 在一个 m*n 的棋盘中的每一个格都放一个礼物，每个礼物都有一定的价值（价值大于0）.你可以从棋盘的左上角开始拿各种里的礼物，并每次向右或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及上面个的礼物，请计算你最多能拿走多少价值的礼物？

思路：

动态规划，dp[i][j]表示从左上角移动到(i,j)时，最大礼物价值。由于只能向右或者向下，则dp[i][j]的值就是左边一个和上边一个中的最大值，再加上当前values[i][j]的值,即dp[i][j] = Math.max(left, up) + values[i][j]。

代码：

    private static int getMaxVal(int[][] values, int rows, int cols) {
        if (values == null || rows <= 0 || cols <= 0) {
            return -1;
        }
        int[][] dp = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int left = 0;
                int up = 0;
                if (i > 0) {
                    left = dp[i - 1][j];
                }
                if (j > 0) {
                    up = dp[i][j - 1];
                }
                dp[i][j] = Math.max(left, up) + values[i][j];
            }
        }
        return dp[rows - 1][cols - 1];//返回礼物最大值
    }