礼物的最大价值

---

题目：

题解

1、动态规划

• 解题思路：

  • 

• 复杂度分析：

  • 时间复杂度 O(MN) ： M, N 分别为矩阵行高、列宽；动态规划需遍历整个 grid 矩阵，使用 O(MN) 时间。
  • 空间复杂度 O(1) ： 原地修改使用常数大小的额外空间。

• 代码：

  // 动态规划，多开一行一列的空间
  class Solution {
      public int maxValue(int[][] grid) {
          int m = grid.length;
          int n = grid[0].length;
          //max[i][j]表示从grid[0][0]到grid[i - 1][j - 1]时的最大价值
          int[][] max = new int[m + 1][n + 1];
          for (int i = 1; i <= m; i++) {
              for (int j = 1; j <= n; j++) {
                  max[i][j] = Math.max(max[i][j - 1] ,max[i - 1][j])  + grid[i - 1][j - 1];
              }
          }
          return max[m][n];
      }
  }