题目链接

题意

题意就是在一个二维矩阵中，从左上角出发，到达右下角，每次移动只能向右或者向下移动。求能从这个二维矩阵中获得的最大值。

题解

这里我们不能一开始不能根据题目的描述就代入的思考从左上角如何移动到右下角获得最大值。而是应该关注最终的问题，如何在矩阵中的右下角单元格处获得最大和。
那么此时变换思维，到矩阵中的每一个单元格处看，该单元处能获得的和，只能是来自于其上方的单元格，或者是其左边的单元格。那么到这里状态转移方程就很明了了。

代码

  1. class Solution {
  2. public:
  3.     int maxValue(vector<vector<int>>& grid) {
  4.         int row = grid.size();
  5.         int col = grid[0].size();
  6.         vector<int> vec(col+1);
  7.         for (int i = 0; i < row; i++) {
  8.             for (int j = 1; j < col+1; j++) {
  9.                 //这里根据题意，可以节省空间，只用一维向量就可以
  10.                 vec[j] = max(vec[j], vec[j-1]) + grid[i][j-1];
  11.             }
  12.         }
  13.         return vec[col];
  14.     }
  15. };