【动态规划专题】剑指 Offer 47. 礼物的最大价值

共以下 3 个回答

• JustRtn 普通 2023年9月18日 下午3:33

  二维数组

  class Solution {
  public:
      int maxValue(vector<vector<int>>& grid) {
          int m = grid.size();
          int n = grid[0].size();
          vector<vector<int>> dp(m, vector<int>(n, 0));
          dp[0][0] = grid[0][0];
          for(int i=1; i < n; i++) {
              dp[0][i] = dp[0][i-1] + grid[0][i];
          }
          for (int i = 1; i < m; i++) {
              dp[i][0] = dp[i-1][0] + grid[i][0];
          }
          for (int i = 1; i < m; i++) {
              for (int j = 1; j < n; j++) {
                  dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
              }
          }
          return dp[m-1][n-1];
      }
  };
  

  一维数组

  class Solution {
  public:
      int maxValue(vector<vector<int>>& grid) {
          int m = grid.size();
          int n = grid[0].size();
          vector<int> dp(n);
          dp[0] = grid[0][0];
          for (int i=1; i < n; i++) {
              dp[i] = dp[i-1] + grid[0][i];
          }
          for (int i = 1; i < m; i++) {
              dp[0] += grid[i][0];
              for (int j = 1; j <n; j++) {
                  dp[j] = max(dp[j-1], dp[j]) + grid[i][j];
              }
          }
          return dp[n-1];
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 别扒拉我 普通 2023年9月14日 上午12:39

  状态定义：dp[i][j]为从左上角到grid[i][j]的礼物最大值
  转移方程：dp[i][j]=max(dp[i-1][j], dp[i][j-1])
  初始状态：左边和上边

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

  空间优化，使用一个数组

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

  0 赞同 0 条回复

  登录以回复
• 塔底的仰望 永久会员 2023年9月13日 下午9:38

  时间复杂度O(mn), 空间复杂度O(n)

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

  0 赞同 0 条回复

  登录以回复