当前位置：
  1. 首页
  2. 剑指offer刷题第三期
  3. 问题详情

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

本问题对应课程链接：剑指offer刷题第三期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi
122 14

共以下 14 个回答

  • 招舟子 普通 2023年12月6日 下午3:14

    class Solution {
    public int jewelleryValue(int[][] frame) {
    int[][] dp = new int[frame.length][frame[0].length];
    dp[0][0] = frame[0][0];
    for(int i =1;i<frame.length;i++){
    dp[i][0] = dp[i-1][0]+frame[i][0];
    }
    for(int i =1;i<frame[0].length;i++){
    dp[0][i] = dp[0][i-1]+frame[0][i];
    }
    for(int i =1;i<frame.length;i++){
    for(int j =1;j<frame[0].length;j++){
    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+frame[i][j];
    }
    }
    return dp[frame.length-1][frame[0].length-1];
    }
    }
    简单动态规划

    0 赞同 0 条回复
  • 九号球 普通 2023年12月3日 上午9:57

    “`java
    class Solution {
    public int jewelleryValue(int[][] frame) {
    //dp[i][j]表示到达i,j位置，路线的最大值，则dp[i][j] = Math.max(dp[i – 1][j], dp[i][j -1]) + frame[i][j];
    //因为路径上没有负数，所以dp[m-1][n-1]就是最大值
    int m = frame.length;
    int n = frame[0].length;
    //优化成一维数组
    int[] dp = new int[n];
    dp[0] = frame[0][0];
    for (int j = 1; j < n; j++) { dp[j] = dp[j - 1] + frame[0][j]; } for (int i = 1; i < m; i++) { for(int j = 0; j < n; j++) { dp[j] = Math.max(j > 0 ? dp[j – 1] : 0, dp[j]) + frame[i][j];
    }
    }
    return dp[n – 1];
    }
    }

    0 赞同 0 条回复
  • 张开怀 普通 2023年7月24日 下午3:02 
    class Solution{
public:
       int maxValue(vector<vector<int>>& grid){
              int n = grid.size();
              int m = grid[0].size();
              vector<int> dp(m,0);
              dp[0] = grid[0][0];
              for(int j=1;j<m;j++){
                     dp[j] = dp[j-1] + grid[0][j];
              }
              for (int i=1; i<n; i++){
                     dp[0] += grid[i][0];
                     for(int j=1; j<m; j++){
                            dp[j] = max(dp[j-1], dp[j] + grid[i][j])
                     }
              }
              return dp[m-1];
       }
};

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

    0 赞同 0 条回复
  • 哈哈哈哈开开心心 普通 2023年7月23日 上午12:43 
    class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [0] * n

        dp[0] = grid[0][0]

        for i in range(1, n):
            dp[i] = dp[i - 1] + grid[0][i]

        for i in range(1, m):
            dp[0] += grid[i][0]
            for j in range(1, n):
                dp[j] = max(dp[j], dp[j - 1]) + grid[i][j]

        return dp[n - 1]

    使用滚动数组

    0 赞同 0 条回复
  • Dsjh 普通 2023年7月23日 上午12:37

    MY

    // 最大路径和
class Solution {
public:
    vector<vector<int>> v;
    int maxValue(vector<vector<int>>& grid) {
        v = vector<vector<int>>(grid.size(),vector<int>(grid[0].size(),INT_MIN));
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(!i && !j){
                    v[i][j] = grid[i][j];
                }
                else{
                    if(i) v[i][j] = max(v[i][j],v[i-1][j]+grid[i][j]);
                    if(j) v[i][j] = max(v[i][j],v[i][j-1]+grid[i][j]);
                }
            }
        }
        return v[grid.size()-1][grid[0].size()-1];
    }
};
    0 赞同 0 条回复
  • BOZ 普通 2023年7月22日 上午10:51

    【思路】DP
    【复杂度】时间O(mn)，空间O(m)/O(n)

    class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        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] = std::max(dp[j - 1], dp[j]) + grid[i][j];
        }
        return dp[n - 1];
    }
};
    0 赞同 0 条回复
  • 花老爷 普通 2023年7月21日 下午12:43

    动态规划
    时间：O(mn)
    空间：O(1)，不考虑grid

    class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int i = 1; i < n; i++) {
            grid[0][i] += grid[0][i - 1];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.max(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[m - 1][n - 1];
    }
}
    0 赞同 0 条回复
  • 局外人 普通 2023年7月20日 下午6:08

    思路：动态规划——因为是向下或向右移动，因此将上侧和左侧的边界dp数组赋予初值，然后根据向下或向右的值进行状态转移
    时间复杂度：O(mn) 空间复杂度：O(mn)

    class Solution {
    public int  maxValue(int[][] grid) {

        int m=grid.length, n=grid[0].length;
        if(m==0 || n==0)    return 0;

        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];
    }
}
    0 赞同 0 条回复
  • Ming 普通 2023年7月20日 下午4:44 
     public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n+1];
        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] = 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年7月20日 上午8:39

    “`C++
    int maxValue(vector>& grid) {
    int m = grid.size();
    int n = grid[0].size();

    std::vector<std::vector<int>> dp(m, std::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] = std::max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    }
}

return dp[m - 1][n - 1];

    }

    “`

    0 赞同 0 条回复
  • mpweixin用户 永久会员 2023年7月19日 下午5:45 
    //时间O(mn)  空间O(mn)
class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int 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 i = 1;i < n;i++){
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }

        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];
    }
}
    0 赞同 0 条回复
  • 小吕 普通 2023年7月18日 下午10:15

    c++实现
    int maxValue(vector<vector>& grid) {
    int line = grid[0].size();
    int row = grid.size();
    int dp[row][line];
    dp[0][0] = grid[0][0];
    for(int i = 1;i<row;i++)
    {
    dp[i][0] = grid[i][0]+dp[i-1][0];
    }
    for(int i = 1;i<line;i++)
    {
    dp[0][i] = grid[0][i]+dp[0][i-1];
    }
    for(int i = 1;i<row;i++)
    {
    for(int j = 1;j<line;j++)
    {
    dp[i][j] = max(dp[i-1][j],dp[i][j-1])+grid[i][j];
    }
    }
    return dp[row-1][line-1];
    }

    0 赞同 0 条回复
  • yxy 普通 2023年7月18日 下午5:19

    时间复杂度O(mn)

    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));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==0&&j==0) dp[i][j]=grid[i][j];
                else if(i==0) dp[i][j]=dp[i][j-1]+grid[i][j];
                else if(j==0) dp[i][j]=dp[i-1][j]+grid[i][j];
                else
                    dp[i][j]=max(dp[i-1][j], dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};
    0 赞同 0 条回复
  • Yodl. 普通 2023年7月18日 下午2:11 
    //和day26的LeetCode 64. 最小路径和思路一样
//时间复杂度O(mn) 空间复杂度O(1) 
class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        for(int i=1;i<m;i++)
        {
            grid[i][0]=grid[i-1][0]+grid[i][0];
        }
        for(int j=1;j<n;j++)
        {
            grid[0][j]=grid[0][j-1]+grid[0][j];
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                grid[i][j]=max(grid[i-1][j],grid[i][j-1])+grid[i][j];//dp[i][j]=max(dp[i-1][j],dp[i][j-1])+dp[i][j];
            }
        }
        return grid[m-1][n-1];
    }
};
    0 赞同 0 条回复

# 回答此问题

后才能回答