[剑指 Offer 第 2 版第 47 题] “礼物的最大值”做题记录

第 47 题：礼物的最大价值

传送门：礼物的最大价值，牛客网 online judge 地址。

在一个 m×n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。

你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格直到到达棋盘的右下角。

给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？

注意：

• m,n>0

样例：

输入： [ [2,3,1], [1,7,1], [4,6,1] ]

输出：19

解释：沿着路径 2→3→7→6→1 可以得到拿到最大价值礼物。

思路：动态规划。礼物要么来自左边一格，要么来自上面一格，两者取最大。要特殊判断的就是边界情况。另外可以使用一维数组完成动态规划。如果可以修改 grid，直接在 grid 上修改就可以了，不用辅助空间。

• 动态规划。
• 可以尽量减少空间复杂度。

Python 代码：

  class Solution(object):
        def getMaxValue(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """

            m = len(grid)
            if m == 0:
                return 0
            n = len(grid[0])

            dp = [None for _ in range(n)]

            dp[0] = grid[0][0]
            for i in range(1, n):
                dp[i] = dp[i - 1] + grid[0][i]

            for i in range(1, m):
                for j in range(n):
                    if j == 0:
                        dp[j] += grid[i][0]
                    else:
                        dp[j] = grid[i][j] + max(dp[j - 1], dp[j])

            return dp[n - 1]

Java 代码：

  public class Solution {

        public int getMaxValue(int[][] matrix) {
            int row = matrix.length;
            if (row == 0) {
                return 0;
            }
            int col = matrix[0].length;
            int[][] dp = new int[row][col];
            dp[0][0] = matrix[0][0];

            for (int j = 1; j < col; j++) {
                dp[0][j] = dp[0][j - 1] + matrix[0][j];
            }
            for (int i = 1; i < row; i++) {
                dp[i][0] = dp[i - 1][0] + matrix[i][0];
                for (int j = 1; j < col; j++) {
                    dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
                }
            }
            return dp[row - 1][col - 1];
        }

        public static void main(String[] args) {
            int[][] matrix = new int[][]{
                    {1, 10, 3, 8},
                    {12, 2, 9, 6},
                    {5, 7, 4, 11},
                    {3, 7, 16, 5}
            };
            Solution solution = new Solution();
            int maxValue = solution.getMaxValue(matrix);
            System.out.println(maxValue);
        }
    }

Java 代码：

  public class Solution2 {

        public int getMaxValue(int[][] matrix) {
            int row = matrix.length;
            if (row == 0) {
                return 0;
            }
            int col = matrix[0].length;
            int[] dp = new int[col];
            dp[0] = matrix[0][0];

            for (int j = 1; j < col; j++) {
                dp[j] = dp[j - 1] + matrix[0][j];
            }
            for (int i = 1; i < row; i++) {
                dp[0] = dp[0] + matrix[i][0];
                for (int j = 1; j < col; j++) {
                    dp[j] = Integer.max(dp[j], dp[j - 1]) + matrix[i][j];
                }
            }
            return dp[col - 1];
        }

        public static void main(String[] args) {
            int[][] matrix = new int[][]{
                    {1, 10, 3, 8},
                    {12, 2, 9, 6},
                    {5, 7, 4, 11},
                    {3, 7, 16, 5}
            };
            Solution2 solution2 = new Solution2();
            int maxValue = solution2.getMaxValue(matrix);
            System.out.println(maxValue);
        }
    }

Java 代码：

  public class Solution3 {

        public int getMaxValue(int[][] matrix) {
            int row = matrix.length;
            if (row == 0) {
                return 0;
            }
            int col = matrix[0].length;
            int[] dp = new int[col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    dp[j] = Integer.max(dp[j], j - 1 < 0 ? 0 : dp[j - 1]) + matrix[i][j];
                }
            }
            return dp[col - 1];
        }

        public static void main(String[] args) {
            int[][] matrix = new int[][]{
                    {1, 10, 3, 8},
                    {12, 2, 9, 6},
                    {5, 7, 4, 11},
                    {3, 7, 16, 5}
            };
            Solution3 solution3 = new Solution3();
            int maxValue = solution3.getMaxValue(matrix);
            System.out.println(maxValue);
        }
    }

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/