1. 首页
  2. 剑指offer经典面试题

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

[剑指 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/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3293.html

« [剑指 Offer 第 2 版第 46 题] “把数字翻译成字符串”做题记录
[剑指 Offer 第 2 版第 48 题] “最长不重复字符串的子字符串”做题记录»

相关推荐

QR code