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

晓宇普通 2024年12月30日下午9:03

// 类似最小路径和
class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        if(frame.empty() || frame[0].empty()) return 0;
        // 定义dp
        // 写出dp公式 dp[i][j] += max(dp[i-1][j], dp[i][j-1])
        // 确定初值
        int m = frame.size(), 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] = frame[i][0] + dp[i - 1][0];
        for(int j = 1; j < n; j++) 
            dp[0][j] += frame[0][j] + dp[0][j - 1];
        for(int i = 1;i < m; i++){
            for(int j = 1;j < n; j++){
                dp[i][j] = frame[i][j] + max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
    // o(m * n) o(m * n)
};

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        if(frame.empty() || frame[0].empty()) return 0;
        // 定义dp
        // 写出dp公式 dp[i][j] += max(dp[i-1][j], dp[i][j-1])
        // 确定初值
        // 优化：一维dp,当前行的dp最多只用到上一行
        int m = frame.size(), n = frame[0].size();
        vector <int> dp(n);
        dp[0] = frame[0][0];

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

        }
        return dp[n - 1];
    }
    // o(m * n) o(m)
};

0 赞同 0 条回复

陆狗陆狗普通 2024年12月26日下午9:45

解题思路
– 类似于最小路径和，这里就不过多解答了
【题解1】

class Solution {
    public int jewelleryValue(int[][] frame) {
        // 1、dp[i][j] 标识 i和j的最高价值珠宝
        // 2、 dp[i][j]=max(dp[i-1][j],dp[i,j-1])+frame[i][j]
        // 3、第一行和第一列是可以初始化的

        int[][] dp = new int[frame.length][frame[0].length];
        // 第0行
        dp[0][0] = frame[0][0];
        for (int j = 1; j < frame[0].length; j++) {
            // 【错误点】 写成了dp[0][j] = dp[0][j - 1] + frame[0][j-1];
            dp[0][j] = dp[0][j - 1] + frame[0][j];
        }
        // 第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.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];
    }
}

错误点1：写成了dp[0][j] = dp[0][j – 1] + frame[0][j-1];

0 赞同 0 条回复

Aatorx 永久会员 2024年12月23日上午11:06

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

时间复杂度O(N∗M)，空间复杂度O(1)。

0 赞同 0 条回复

Pendulumpal 普通 2024年12月22日下午5:54

O(mn),将一步步求最大

class Solution {
    public int jewelleryValue(int[][] frame) {
        int m=frame.length;
        int n=frame[0].length;
        int[][] dp=new int[m][n];
        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 && j!=0)dp[i][j]=dp[i][j-1]+frame[i][j];
                else if(i!=0 && j==0)dp[i][j]=dp[i-1][j]+frame[i][j];
                else dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j])+frame[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

0 赞同 0 条回复

秋山丽奈普通 2024年12月22日下午4:58

思路：与最小路径和相似

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

        int col = frame.length;
        int row = frame[0].length;

        int[][] result = new int[col][row];

        result[0][0] = frame[0][0];

        for(int currentCol = 1; currentCol < col; currentCol ++){
            result[currentCol][0] = result[currentCol-1][0] + frame[currentCol][0];
        }

        for(int currentRow = 1; currentRow < row; currentRow ++){
            result[0][currentRow] = result[0][currentRow-1] + frame[0][currentRow];
        }

        for(int currentCol = 1; currentCol < col; currentCol ++){
            for(int currentRow = 1; currentRow < row; currentRow ++){
                result[currentCol][currentRow] = Math.max(result[currentCol-1][currentRow]+frame[currentCol][currentRow], result[currentCol][currentRow-1]+frame[currentCol][currentRow]);
            }
        }

        return result[col-1][row-1];

    }

}

0 赞同 0 条回复

苯庸普通 2024年12月21日下午9:32

class Solution {
public int jewelleryValue(int[][] frame) {
int m = frame.length, n = frame[0].length;
int[][] dp = new int[m][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 j = 1; j < n; j++){
dp[0][j] = dp[0][j-1] + frame[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]) + frame[i][j];
}
}
return dp[m-1][n-1];
}
}
时间：O（mn）
空间：o（mn）

0 赞同 0 条回复

Kisara 普通 2024年12月21日下午8:27

和前面有一题一样的解法

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

        int[] dp=new int[frame[0].length];
        dp[0]=frame[0][0];
        for(int i=1;i<frame[0].length;i++){
            dp[i]=dp[i-1]+frame[0][i];
        }

        for(int i=1;i<frame.length;i++){
            dp[0]+=frame[i][0];
            for(int j=1;j<frame[0].length;j++){
                dp[j]=Math.max(dp[j-1]+frame[i][j],dp[j]+frame[i][j]);
            }
        }
        return dp[frame[0].length-1];
    }
}

0 赞同 0 条回复

月下足迹普通 2024年12月21日上午11:48

//和机器人走格子一样解法
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 i = 1; i < m; i++) {
dp[i][0] = frame[i][0] + dp[i-1][0];
}
for (int j = 1; j < n; j++) {
dp[0][j] = frame[0][j] + dp[0][j-1];
}

    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];
}

0 赞同 0 条回复

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

共以下 8 个回答

# 回答此问题取消回复

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

共以下 8 个回答

# 回答此问题 取消回复

# 回答此问题取消回复