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

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];
}