1. 礼物的最大价值

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

  1. 示例 1:
  3. 输入: 
  4. [
  5.   [1,3,1],
  6.   [1,5,1],
  7.   [4,2,1]
  8. ]
  9. 输出: 12
  10. 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

思路：

  • 动态规划
  • 设置一个与初始数组规格完全相同的新数组dp
  • 这个数组进行遍历使得每个位置都是以要求的方式到达该位置所能得到礼物的最大值
  • 最终返回dp矩阵中最右下角的值
    class Solution {
  public int maxValue(int[][] grid) {
      // 使用动态规划,每个位置的值为能走到该位置所能拿到礼物的最大值
      int[][] dp = new int[grid.length][grid[0].length];
      dp[0][0] = grid[0][0];
      int left;
      int up;
      for(int i=0;i<grid.length;i++){
          for(int j=0;j<grid[0].length;j++){
              if(i-1<0){
                  up = 0;
              }else{
                  up = dp[i-1][j];
              }
              if(j-1<0){
                  left = 0;
              }else{
                  left = dp[i][j-1];
              }
              dp[i][j] = Math.max(up,left) + grid[i][j];
          }
      }
      return dp[grid.length-1][grid[0].length-1];
  }
}