动态规划——礼物的最大价值

1.问题描述

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

示例1:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出:12
解释:路径1——3——5——2——1可以拿到最大价值的礼物.

2.解决方案

这个问题与找三角形的最小路径在本质上是一样的问题,可以用动态规划算法解决。

用count[ i ][ j ] 表示从左上角到第i行第j列这个格子拿到的最大的礼物价值。

(1)自顶向下 考虑从左上角出发,计算出到每个棋盘格的最大礼物价值。

一般情况下,有递推公式: count[ i ][ j ] = max{ count[ i ][ j-1 ], count[ i - 1 ][ j ] }+grid[ i ][ j ] 对于特殊情况,即 i = 0 或 j = 0 时进行特殊处理。

int maxValue(vector<vector<int>>& grid)
{
          
   
    int rows=grid.size();
    int cols=grid[0].size();
    vector<vector<int>> count(rows);

    count[0].push_back(grid[0][0]);//初始化count数组

    for(int i=0;i<rows;i++)
    {
          
   
        for(int j=0;j<cols;j++)
        {
          
   
            if(i==0&&j==0)
                ;//前面已经进行过初始化了
            else if(i==0)
                count[i].push_back(count[i][j-1]+grid[i][j];
            else if(j==0)
                count[i].push_back(count[i-1][j]+grid[i][j];
            else
                count[i].push_back(max(count[i-1][j],count[i][j-1])+grid(i,j));
        }
    }
    return count[rows-1][cols-1];
}

(2)自底向上 考虑从右下角出发,计算出到每个棋盘格的最大价值。

一般情况下,有递推公式: count[ i ][ j ] = max{ count[ i ][ j+1 ], count[ i + 1 ][ j ] }+grid[ i ][ j ] 对于某些 i, j 进行特殊处理。

int maxValue(vector<vector<int>>& grid)
{
          
   
    int rows=grid.size();
    int cols=grid[0].size();
    vector<vector<int>> count(rows);

    for(int i=0;i<rows;i++)
        for(int j=0;j<cols;j++)
            count[i].push_back(0);//初始化count数组,方便后面的操作
    count[rows-1][cols-1]=grid[rows-1][cols-1];

    for(int i=rows-1;i>=0;i--)
    {
          
   
        for(int j=cols-1;j>=0;j--)
        {
          
   
            if(i==rows-1&&cols-1)
                ;
            else if(i==rows-1)
                count[i][j]=count[i][j+1]+grid[i][j];
            else if(j==cols-1)
                count[i][j]=count[i+1][j]+grid[i][j];
            else
                count[i][j]=max(count[i+1][j],count[i][j+1])+grid[i][j];
        }
    }
    return count[0][0];
}
经验分享 程序员 微信小程序 职场和发展