/*
f[i][j]表示：从起点到i,j 的可以获取到的最大价值.
递推式：
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + a[i][j];
*/
class Solution {
public:
    int getMaxValue(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        // 申请n+1,m + 1的dp矩阵，可以不用考虑边界情况.
        vector<vector<int>> f = vector<vector<int>>(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + grid[i - 1][j - 1];
        return f[n][m];
    }
};