LeetCode 47. 礼物的最大价值解题思路

面试题47. 礼物的最大价值

题目描述

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

示例 1:

输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

解法

class Solution {
    public int maxValue(int[][] grid) {
      int x = grid.length;
        int y = grid[0].length;
        int[][] dp = new int[x + 1][y + 1];
        for (int i = 1; i <= x; i++) {
            for (int j = 1; j <= y; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[x][y];
    }
}

分析思路

动态规划

从题目中可以看出每一个单元格的元素都和其之前的单元格存在关联,所以这题可以考虑使用动态规划的方式来解决
假设二维数组dp[i][j]表示单元格 (i ,j)(i,j) 的礼物最大累计价值,由于题目说到每次向右或者向下移动一格,所以可以到达整个单元格的方式,只能从上(i,j-1)和左边(i-1,j)的单元格达到,并且取这两个单元格的最大值,并可以推导出公式

dp(i,j)=max[dp(i,j−1),dp(i−1,j)]+grid(i,j)

在具体写法需要考虑,到第一行和第一列的边界问题,因为第一行只能从左边到达,第一列只能从上到达,所以,可以将二维数组的大小初始化的+1,遍历时i,j从1开始,避免从grid(i,j)取值的时,出现越界问题。

最近的文章

链表的快慢指针的使用

链表的快慢指针的使用1.环形链表LeetCode题目141.环形链表题目描述给定一个链表,判断链表中是否有环。为了表示给定链表中的环,我们使用整数pos来表示链表尾连接到链表中的位置(索引从0开始)。如果pos是-1,则在该链表中没有环。示例1:输入:head=[3,2,0,-4],pos=1输出:…

继续阅读