//0048礼物的最大价值
class Solution {
public:
    int getMaxValue(vector<vector<int>>& grid) {
        int r = grid.size(), c = grid[0].size();

        //初始化第一行
        for (int i = 1; i < c; ++i) {
            grid[0][i] += grid[0][i - 1];
        }
        for (int i = 1; i < r; ++i) {
            grid[i][0] += grid[i - 1][0];
        }

        for(int i = 1; i < r; ++i) {
            for(int j = 1; j < c; ++j) {
                grid[i][j] += max(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[r - 1][c - 1];
    }
};