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

Gg 普通 2023年8月7日下午5:48

class Solution {
    // 定义dp数组为当前的礼物最大价值
    public int maxValue(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[0].length; j ++){
                int up = 0;
                if(i-1 >= 0){
                    up = dp[i-1][j];
                }
                int left = 0;
                if(j-1 >= 0){
                    left = dp[i][j-1];
                }
                dp[i][j] = Math.max(up,left) + grid[i][j];
            }
        }
        return dp[grid.length-1][grid[0].length-1];
    }
}

0 赞同 0 条回复

宁永久会员 2023年3月14日下午3:06

一维注意初始化

class Solution {
    public int maxValue(int[][] grid) {
        //相当于最大路径和
        //当前值加上左侧或者上方的最大值。
        int m = grid.length;
        int n = grid[0].length;
        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] + dp[0];
            for(int j = 1; j < n; j++){
                dp[j] = Math.max(dp[j - 1], dp[j]) + grid[i][j];
            }
        }
        return dp[n - 1];
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月18日下午6:02

def maxValue(grid: list[list[int]]) -> int:
    m = len(grid) # 行
    n = len(grid[0]) # 列

    # 定义dp，到达dp[i]表示某一行的i列所在位置的最小路径和
    # 每行动态更新
    dp = [-1] * n
    dp[0] = grid[0][0]
    # 初始化dp
    for _ in range(1,n):
        dp[_] = dp[_-1] + grid[0][_]
    for i in range(1,m):
        for j in range(0,n):
            # 对于第一列的元素dp[0]只能向下走，需要单独计算
            if j == 0:
                dp[j] = dp[j] + grid[i][j]
            else:
                dp[j] = max(dp[j-1],dp[j]) + grid[i][j]

    return dp[-1]

0 赞同 0 条回复

lucca 普通 2023年1月18日下午1:42

和LeetCode 64. 最小路径和同理，最小值改为最大值即可

时间复杂度 O(NM)
空间复杂度 O(1)

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

0 赞同 0 条回复

@ 普通 2022年12月20日上午9:43

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public int maxValue(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;


        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; 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 - 1][j], grid[i][j - 1]);


            }
        }


        return grid[row - 1][col - 1];
    }
}

0 赞同 0 条回复

T 普通 2022年11月30日下午8:59

跟路径和那题一样

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] + grid[i][j];
                } else if(j == 0) {
                    grid[i][j] = grid[i - 1][j] + grid[i][j];
                }else {
                    grid[i][j] = Math.max(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
                }
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

0 赞同 0 条回复

y 普通 2022年11月27日下午3:48

var maxValue = function(grid) {
   let m = grid.length;
   let n = grid[0].length;
   let dp = Array(m).fill(0).map(item => Array(n).fill(0));
   dp[0][0] = grid[0][0]

   for (let i = 1; i < m; i++) {
       dp[i][0] = dp[i - 1][0] + grid[i][0];
   }

   for (let j = 1; j < n; j++) {
       dp[0][j] = dp[0][j - 1] + grid[0][j]
   }

   for (let i = 1; i < m; i++) {
       for (let 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];
};

时间：O(n*m)

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月25日下午10:17

时间复杂度为O(mn),空间复杂度为O（1）
之前题目的优化版本

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

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月24日下午11:18

二维数组。时间复杂度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];
    }
}

滚动数组

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n + 1];
        //滚动数组。
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                dp[j] = Math.max(dp[j-1],dp[j]) + grid[i-1][j-1];
            }
        }
        return dp[n];
    }
}

0 赞同 0 条回复

青木普通 2022年11月24日下午10:12

/**
    感觉和之前做的题类似，所以想用一下优化
    我们只需要比较dp[j-1] 和 dp[j]就可以了，因为dp是随时更新的，
    因此dp[j-1]是已经更新过的值，所以可以直接和dp[j]进行比较，哪个大加那个

    时间O(m*n)
    空间O(n)
 */

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

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

0 赞同 0 条回复

just 普通 2022年11月24日下午7:59

//动态规划
class Solution {
public:
int maxValue(vector<vector>& grid) {
int m=grid.size(),n=grid[0].size();
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]+=max(grid[i-1][j],grid[i][j-1]);
}
}
return grid[m-1][n-1];
}
};

0 赞同 0 条回复

Mooby 普通 2022年11月24日上午11:06

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        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] = Math.max(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
        return dp[n - 1];
    }
}

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

0 赞同 0 条回复

Tolkien 永久会员 2022年11月24日上午1:00

/**
     * 1. dp数组含义：从(0,0)到(i-1, j-1)的所有路径中最大的权重和为dp[i][j]
     * 2. 关系式：dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])+grid[i][j])
     * 3. 初始化：dp[i][0] = dp[i-1][0], dp[0][j] = dp[0][j-1]
     */
    public static 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 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];
    }

    public static int maxValueOptimized(int[][] grid) {
        int n = grid[0].length;
        int m = grid.length;

        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] = dp[0] + grid[i][0];
            for (int j = 1; j < n; j++) {
                dp[j] = Math.max(dp[j-1], dp[j])+grid[i][j];
            }
        }

        return dp[n-1];
    }

0 赞同 0 条回复

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

共以下 13 个回答

和LeetCode 64. 最小路径和同理，最小值改为最大值即可

# 回答此问题取消回复

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

共以下 13 个回答

和LeetCode 64. 最小路径和 同理，最小值改为最大值即可

# 回答此问题 取消回复

和LeetCode 64. 最小路径和同理，最小值改为最大值即可

# 回答此问题取消回复