招舟子普通 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 条回复

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

共以下 14 个回答

MY

# 回答此问题取消回复

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

共以下 14 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复