题解 | #礼物的最大价值#

礼物的最大价值：最直观的想法是，使用二维数组dp[i][j]表示第i行第j列所能拿的礼物的最大价值，首先初始化第一行和第一列，其是当前行(列)前一个最大价值与当前元素之和，接着从左向右从上向下遍历，其中dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j]，最后返回dp[m-1][n-1]即可。

int maxValue(vector<vector<int> >& grid) 
{
   //m表示长 n表示宽
   int m=grid.size(),n=grid[0].size();
   //dp[i][j]表示第i行第j列的所能拿的礼物的最大价值
   vector<vector<int>> dp(m,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]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];
   return dp[m-1][n-1];
}