works/solutions/leetcode/cpp/li-wu-de-zui-da-jie-zhi-lcof.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <vector>

using std::vector;

#include <algorithm>

class Solution
{
public:
    int maxValue(vector<vector<int>> &grid)
    {
        int row_count = grid.size();
        int col_count = grid.front().size();

        for (int i = 1; i < row_count; i++)
        {
            grid[i][0] = grid[i - 1][0] + grid[i][0];
        }

        for (int j = 1; j < col_count; j++)
        {
            grid[0][j] = grid[0][j - 1] + grid[0][j];
        }

        for (int i = 1; i < row_count; i++)
        {
            for (int j = 1; j < col_count; j++)
            {
                grid[i][j] = std::max(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[row_count - 1][col_count - 1];
    }
};