精华内容
下载资源
问答
  • 在一个m*n的棋盘上每格都有一个礼物,价值都大于0,从左上角开始拿格子里的礼物,直到到右下角,求最大价值礼物为多少。 求最大价值礼物,二维矩阵首先想到这是不是回溯法,但并没有出现失败的情况,因为不到...

    在一个mn的棋盘上每格都有一个礼物,价值都大于0,从左上角开始拿格子里的礼物,直到到右下角,求最大价值的礼物为多少。
    在一个m
    n的棋盘上每格都有一个礼物,价值都大于0,从左上角开始拿格子里的礼物,直到到右下角,求最大价值的礼物为多少。
    dp[i][j]表示这个位置能拿到的最大价值,他怎么得到呢,可能由它上面得到,可能从左边得到所以dp[i][j]=max(dp[i-1][j]+num[i][j],dp[i][j-1]+nums[i][j])
    这个不太好优化空间,因为如果要优化,需要从右开始,但是这个是从左开始的,所以很难办。

    class Solution {
        public int maxValue(int[][] grid) {
            int[][] dp=new int[grid.length+1][grid[0].length+1];
            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]+grid[i-1][j-1],dp[i][j-1]+grid[i-1][j-1]);
                }
            }
            return dp[grid.length][grid[0].length];
        }
    }
    
    展开全文
  • 礼物最大价值

    2018-07-17 08:54:53
    题目:在一个mxn的棋盘的每一个都放有一个礼物,每个礼物都有一定的价值价值大于0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格,知道到达棋盘的右下角。给定一个棋盘及其上面的礼物,...

    题目:在一个mxn的棋盘的每一个都放有一个礼物,每个礼物都有一定的价值(价值大于0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格,知道到达棋盘的右下角。给定一个棋盘及其上面的礼物,请计算你最多能达到多少价值的礼物。

    方法一:动态规划(二维数组存储)

    int getMaxValue_solution1(const int* values, int rows, int cols)
    {
        if(values == nullptr || rows <= 0 || cols <= 0)
            return 0;
        int** maxValues = new int*[rows];
        for(int i = 0; i < rows; ++i)
            maxValues[i] = new int[cols];
        for(int i = 0; i < rows; ++i)
        {
            for(int j = 0; j < cols; ++j)
            {
                int left = 0;
                int up = 0;
                if(i > 0)
                    up = maxValues[i - 1][j];
                if(j > 0)
                    left = maxValues[i][j - 1];
                maxValues[i][j] = std::max(left, up) + values[i * cols + j];
            }
        }
        int maxValue = maxValues[rows - 1][cols - 1];
        for(int i = 0; i < rows; ++i)
            delete[] maxValues[i];
        delete[] maxValues;
        return maxValue;

    }

     

    方法二:动态规划(一维数组存储)

    int getMaxValue_solution2(const int* values, int rows, int cols)
    {
        if(values == nullptr || rows <= 0 || cols <= 0)
            return 0;
        int* maxValues = new int[cols];
        for(int i = 0; i < rows; ++i)
        {
            for(int j = 0; j < cols; ++j)
            {
                int left = 0;
                int up = 0;
                if(i > 0)
                    up = maxValues[j];
                if(j > 0)
                    left = maxValues[j - 1];
                maxValues[j] = std::max(left, up) + values[i * cols + j];
            }
        }
        int maxValue = maxValues[cols - 1];
        delete[] maxValues;
        return maxValue;
    }

    展开全文
  • 走到当前格时累计礼物最大价值为 走到**当前格的左一格(dp[i][j-1])或上一格(dp[i-1][j])时累计礼物最大价值加上当前格礼物(grid[i-1][j-1])**的价值 dp从(1,1)开始索引,这样确保第一个值等于grid中的第一个值。这...

    在这里插入图片描述
    思路
    转移方程:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
    走到当前格时累计礼物最大价值为 走到**当前格的左一格(dp[i][j-1])上一格(dp[i-1][j])时累计礼物最大价值加上当前格礼物(grid[i-1][j-1])**的价值

    dp(1,1)开始索引,这样确保第一个值等于grid中的第一个值。这也是为什么dp数组要进行扩容
    在这里插入图片描述

    class Solution {
    public:
        int maxValue(vector<vector<int>>& grid) {
            int n = grid.size();
            int m = grid[0].size();
            vector<vector<int>> dp;
            dp.resize(n+1, vector<int>(m+1));    // 扩容
    
            for(int i=1; i<=n; i++){
                for(int j=1;j<=m;j++){
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];      
                }
            }
    
            return dp[n][m];
    
        }
    };
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,499
精华内容 3,399
关键字:

礼物的最大价值