剑指 Offer 47. 礼物的最大价值

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

解题思路

解法1：
1.我们设定，dp[i][j]为位置到达（i，j）位置所能获取的最大收获
2.分析题意，每次移动只能向下或者向右移动，因此dp[i][j]与dp[i-1][j]和dp[i][j-1]有关
3.推导可知，状态转移方程为：dp[i][j]=max（dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]）
此解法，时间复杂度和空间复杂度都为O(mn)，mn分别为二维数组的行和宽的长度

image.png

解法2：
1.由解法1可知，dp[i][j]=max（dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]）推导公式中，其实grid每次我们用的是当前的元素grid[i][j]，而dp二维数组，我们每次用到的是dp[i-1][j]和dp[i][j-1]
2.所以这里想到实际上空间复杂度是可以优化的，dp的二维数组其实可以直接复用grid二维数组，即直接在原数组上操作即可

解题遇到的问题

无

后续需要总结学习的知识点

无

##解法1
class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        // 我们设定，dp[i][j]为位置到达（i，j）位置所能获取的最大收获
        // 分析题意，每次移动只能向下或者向右移动，因此dp[i][j]与dp[i-1][j]和dp[i][j-1]有关
        // 推导可知，状态转移方程为：dp[i][j]=max（dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]）
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        int maxSum = dp[0][0];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = Math.max((i > 0 ? dp[i - 1][j] : 0) + grid[i][j],
                        (j > 0 ? dp[i][j - 1] : 0) + grid[i][j]);
                // System.out.println("i" + i + " j" + j + " dp" + dp[i][j]);
                maxSum = Math.max(maxSum, dp[i][j]);
            }
        }
        return maxSum;
    }
}

#j解法2：
class Solution {
    public int maxValue(int[][] grid) {
        int maxSum = grid[0][0];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                grid[i][j] = Math.max((i > 0 ? grid[i - 1][j] : 0) + grid[i][j],
                        (j > 0 ? grid[i][j - 1] : 0) + grid[i][j]);
                maxSum = Math.max(maxSum, grid[i][j]);
            }
        }
        return maxSum;
    }
}