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

hi 普通 2023年11月22日上午10:42

dp数组代表的含义为该位置能获得的最大价值，只能由前两个位置决定
从i = 0, j = 0 开始循环时注意转移方程中 (i – 1) 或（j – 1）可能出现越界的情况，需要提前进行判断，选择合适的方程
i = 0 时，只可能从左边(i, j- 1) 而来，j = 0 时只能从上面(i – 1, j)而来

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

        dp[0][0] = frame[0][0];

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++){
        //(0, 0)到后面遇到i - 1 或 j - 1 的情况怎么处理
                if(i >= 1)  dp[i][j] = max(dp[i][j], dp[i-1][j] + frame[i][j]);
                if(j >= 1)  dp[i][j] = max(dp[i][j], dp[i][j - 1] + frame[i][j]);  
            }     

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

0 赞同 0 条回复

June 普通 2023年10月9日下午9:14

class Solution {
    public int jewelleryValue(int[][] frame) {
        int row = frame.length;
        int col = frame[0].length;
        int[] dp = new int[col]; // 一维
        dp[0] = frame[0][0];
        for(int i=1;i < col ; i++)
            dp[i] = frame[0][i] + dp[i-1];

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

0 赞同 0 条回复

Marshan 普通 2023年8月30日下午7:14

有之前的铺垫会简单些

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[i][j]表示在当前位置能获得的最多价值礼物总和
        // dp[0][0] = grid[0][0];
        // for(int i = 1;i < m;i++){
        //     dp[i][0] = (grid[i][0] + dp[i-1][0]);
        // }
        // for(int j = 1;j < n;j++){
        //     dp[0][j] = (grid[0][j] + dp[0][j-1]);
        // }
        // 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];
        //     }
        // }

        vector<int> dp1(n,0);
        dp1[0] = grid[0][0];
        for(int j = 1;j < n;++j){
            dp1[j] = dp1[j-1] + grid[0][j];
        }
        for(int i = 1;i < m;++i){
            dp1[0] = dp1[0] + grid[i][0];
            for(int j = 1;j < n;j++){
                dp1[j] = max(dp1[j-1],dp1[j]) + grid[i][j];
            }
        }
        return dp1[n-1];
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年8月21日下午1:07

class Solution {
    public int maxValue(int[][] grid) {
        // 输入:
        //[
        //  [1,3,1],
        //  [1,5,1],
        //  [4,2,1]
        //]
        //输出: 12
        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年8月20日下午10:16

一维优化

function maxValue(grid: number[][]): number {
    let m = grid.length, n = grid[0].length;
    let dp = new Array(n).fill(0);
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i === 0 && j === 0) {
                dp[j] = grid[i][j];
            } else if (i === 0) {
                dp[j] = grid[i][j] + dp[j - 1];
            } else if (j === 0) {
                dp[j] += grid[i][j];
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
    }
    return dp[n - 1];
};

0 赞同 0 条回复

北辰普通 2023年8月16日下午4:14

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

时间复杂度：O（m*n）

0 赞同 0 条回复

Mby 普通 2023年8月14日下午7:45

class Solution {
    public int maxValue(int[][] grid) {
        //优化版
        int n = grid.length;//拿到行数
        int m = grid[0].length;//拿到列数

        int [] dp = new int[m];
        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] = dp[0] + grid[i][0];
            for(int j = 1; j < m; j++){
                dp[j] = Math.max(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1];
        //时间复杂度：O(n*m)
        //空间复杂度：O(n)
    }
}

0 赞同 0 条回复

NullPointerException 普通 2023年8月8日下午4:28

class Solution {
public int maxValue(int[][] grid) {
// 最大价值

int dp[][]=new int [grid.length+1][grid[0].length+1];
for(int i=0;i<dp.length;i++)
{
dp[i][0]=-202;
}
for(int i=0;i<dp[0].length;i++)
{
dp[0][i]=-202;
}
dp[1][1]=grid[0][0];
for(int i=1;i<dp.length;i++)
{
for(int j = 1;j<dp[0].length;j++)
{
if(i1&&j1)
{
continue;
}
dp[i][j]=Math.max(dp[i-1][j]+grid[i-1][j-1],dp[i][j-1]+grid[i-1][j-1]);
}
}
return dp[dp.length-1][dp[0].length-1];
}
}

0 赞同 0 条回复

阿尚普通 2023年8月7日下午4:47

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
       //dp:走到坐标为（i - 1，j - 1）的位置能够获得的最大价值
        int[][] dp = new int[m+1][n+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]) + grid[i - 1][j - 1];
            }
        }

        return dp[m][n];
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年8月7日下午3:12

与最小路径和一样，只不过一个求最小，一个求最大

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年8月6日下午11:14

8.6
Day27：下面是代码

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

0 赞同 0 条回复

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

共以下 11 个回答

# 回答此问题取消回复

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

共以下 11 个回答

# 回答此问题 取消回复

# 回答此问题取消回复