【动态规划专题】剑指 Offer 47. 礼物的最大价值-跟着帅地玩副业，开拓第二曲线PlayOffer

kfaebot 普通 2024年5月11日上午10:15

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m=frame.size();
        int n=frame[0].size();

        vector<vector<int>> dp(m,vector<int>(n));

        //初始化
        dp[0][0]=frame[0][0];
        for(int i=1;i<m;i++){
            dp[i][0]=dp[i-1][0]+frame[i][0];
        }
        for(int i=1;i<n;i++){
            dp[0][i]=dp[0][i-1]+frame[0][i];
        }

        //状态转移方程
        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])+frame[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

0 赞同 0 条回复

Thaddeus 永久会员 2024年5月6日上午9:18

打卡

class Solution {
    public int jewelleryValue(int[][] frame) {
        int m = frame.length, n = frame[0].length;
        int[] dp = new int[n];
        dp[0] = frame[0][0];
        for(int i = 1; i < n; i++) dp[i] = dp[i - 1] + frame[0][i];

        for(int i = 1; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(j == 0) dp[j] = dp[j] + frame[i][j];
                else dp[j] = Math.max(dp[j], dp[j - 1]) + frame[i][j];
            }
        }

        return dp[n - 1];
    }
}

0 赞同 0 条回复

=.= 普通 2024年4月15日下午2:36

class Solution {
public int jewelleryValue(int[][] frame) {
int m = frame.length;
int n = frame[0].length;

    int[][] dp = new int[m][n];
    dp[0][0] = frame[0][0];
    for(int j=1; j<n; j++){
        dp[0][j] = dp[0][j-1] + frame[0][j];
    }
    for(int i=1; i<m; i++){
        dp[i][0] = dp[i-1][0] + frame[i][0];
    }

    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]) + frame[i][j];
        }
    }

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

}

时间：O(mn)
空间：O(mn)

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年4月3日下午1:48

class Solution {
    public int jewelleryValue(int[][] frame) {

        int n = frame.length; //n:行数
        int m = frame[0].length; //m：列数

        int[] dp = new int[m]; //保存一行的值
        dp[0] = frame[0][0];

        // 初始值
        for(int i = 1; i < m; i++){
            dp[i] = dp[i-1]+frame[0][i];
        }

        for(int i = 1; i < n; i++){
            // 下面这个for表示第i行
            dp[0]=dp[0]+frame[i][0]; //第i行最左边的元素
            for(int j = 1; j < m; j++){
                //计算第i行的时候只用到了第i行和第i-1行的数据
                dp[j] = Math.max(dp[j] ,dp[j-1])+frame[i][j];
            }
        }

        return dp[m-1];

    }
}

时间复杂度：O(n*m)
空间复杂度：O(n)

0 赞同 0 条回复

神经蛙普通 2024年4月2日下午11:43

class Solution {
public:
int jewelleryValue(vector<vector>& frame) {
int m = frame.size(), n = frame[0].size();
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i 0 && j 0) continue;
if(i 0) frame[i][j] += frame[i][j – 1] ;
else if(j 0) frame[i][j] += frame[i – 1][j];
else frame[i][j] += max(frame[i][j – 1], frame[i – 1][j]);
}
}
return frame[m – 1][n – 1];
}
};
打卡

0 赞同 0 条回复

方铎码农普通 2024年4月1日下午11:26

class Solution {
    public int jewelleryValue(int[][] frame) {
        int m = frame.length, n = frame[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0 && j == 0) continue;
                if(i == 0) frame[i][j] += frame[i][j-1];
                else if (j == 0) frame[i][j] += frame[i-1][j];
                else frame[i][j] += Math.max(frame[i-1][j],frame[i][j-1]);
            }
        }
        return frame[m-1][n-1];
    }
}

时间复杂度$O(mn)$，空间复杂度$O(1)$

0 赞同 0 条回复

heathhou 普通 2024年4月1日下午10:58

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        if(frame.size() <= 0 || frame[0].size()<=0){
            return 0;
        }
        if(frame[0].size() == 1 && frame[0][0] == 0){
            return 0;
        }

        int m = frame.size();
        int n = frame[0].size();
        // dp: 到位置（i, j）处，所能得到的宝珠的最大价值
        vector<int> dp(n, -1);

        // 状态转移方程
        // dp[j] = max(dp[j-1], dp[j]) + frame[i][j]

        // 初始化
        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){
            dp[0] = dp[0] + frame[i][0];
            for(int j = 1; j < n; ++j){
                dp[j] = max(dp[j-1], dp[j]) + frame[i][j];
            }
        }
        return dp[n-1];
    }
};

0 赞同 0 条回复

Jimmy 普通 2024年4月1日下午10:03

和最小路径和类似

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        for(int i=0;i<frame.size();i++)
        {
            for(int j=0;j<frame[0].size();j++)
            {
                if(i == 0 && j == 0) continue;
                else if(i == 0)frame[i][j] = frame[i][j-1] + frame[i][j];
                else if(j == 0)frame[i][j] = frame[i-1][j] + frame[i][j];
                else frame[i][j] = max(frame[i-1][j],frame[i][j-1])+frame[i][j];
            }
        }
        return frame[frame.size()-1][frame[0].size()-1];
    }
};

0 赞同 0 条回复

云无深雁影普通 2024年4月1日下午3:58

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 j = 1; j < frame[0].length; j++)
dp[0][j] = dp[0][j-1] + frame[0][j];
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];
}
}
//时间Onm
//空间O1

0 赞同 0 条回复

一个达不刘普通 2024年4月1日上午11:52

class Solution {
public:
int jewelleryValue(vector<vector>& frame) {
//细分边界，一一讨论
for(int i=0;i<frame.size();i++){
for(int j=0;j<frame[0].size();j++){
if(i0&& j0) continue;
else if(i0) frame[i][j] = frame[i][j-1] + frame[i][j];
else if(j0) frame[i][j] = frame[i-1][j] + frame[i][j];
else frame[i][j] = max(frame[i-1][j],frame[i][j-1]) + frame[i][j];
}
}
return frame[frame.size()-1][frame[0].size()-1];
}
};

0 赞同 0 条回复

紫芝普通 2024年4月1日上午8:14

时间：O(mn)
空间：O(n)

“`c++
class Solution {
public:
int jewelleryValue(vector>& frame) {
int row = frame.size(), col = frame[0].size();
vector dp(col, 0);
dp[0] = frame[0][0];
for (int j=1; j

0 赞同 0 条回复

Raphtalia. 普通 2024年3月31日下午11:11

class Solution {
public:
int jewelleryValue(vector<vector>& frame) {
int m = frame.size(), n = frame[0].size();
vector<vector> dp(m, vector(n, 0));
int res = 0;
for(int i = 0; i < m; i ++) {
for(int j = 0; j < n; j ++) {
if(i 0 && j 0) dp[i][j] = frame[i][j];
else if(i 0) dp[i][j] = frame[i][j] + dp[i][j – 1];
else if(j 0) dp[i][j] = frame[i][j] + dp[i – 1][j];
else {
dp[i][j] += frame[i][j] + max(dp[i][j – 1], dp[i – 1][j]);
}
res = max(res, dp[i][j]);
}
}
return res;
}
//时间复杂度O(MN),空间复杂度O(MN)
};

0 赞同 0 条回复

王位詮釋普通 2024年3月31日下午8:32

class Solution {
    public int jewelleryValue(int[][] frame){
        int m = frame.length;
        int n = frame[0].length;
        int[] dp = new int[n];
        dp[0] = frame[0][0];
        //初始化
        for(int i = 1;i<n;i++){
            dp[i] = frame[0][i]+dp[i-1];
        }
        for(int i=1;i<frame.length;i++){
            dp[0] = dp[0]+frame[i][0];
            for(int j = 1;j<frame[i].length;j++){
                dp[j] = Math.max(dp[j-1],dp[j])+frame[i][j];
            }
        }
        return dp[n-1];
    }
}
思路：感觉这个题和之前文章里的例题是一种类型，移动方向只能是向下或者向右，所以记录下到第i个位置为止的最大礼物价值，无论某一个位置是否有礼物，都是要到最后frame[n][n]停止，所以最后一个位置的值就是最大价值，直接返回就行。
时间复杂度：O(n2)
空间复杂度：O(n)

0 赞同 0 条回复

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

共以下 13 个回答

# 回答此问题取消回复

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

共以下 13 个回答

# 回答此问题 取消回复

# 回答此问题取消回复