面试题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)取值的时，出现越界问题。