矩阵中每个位置只能往下或者往右移动，那么对于走到该点的路径只可能是从上或者从左。求走到每个点的最优解则为，在上一个点或者左边一个点的最优解加上该点本身值，取其中较大的作为该点的最优解。用一个辅助二维数组存储每个点的最优解，最后可得最大值。

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：时间复杂度为O(mn); m一维大小，n二维大小

C++ 代码

class Solution {
public:
int getMaxValue(vector[HTML_REMOVED]>& grid) {
if(grid.size() == 0) return 0;
vector[HTML_REMOVED]> path(grid.size(),vector[HTML_REMOVED](grid[0].size(),0));
int path1;
path[0][0]=grid[0][0];
for(int i = 1;i[HTML_REMOVED]path[j-1][i]?path[j][i-1]:path[j-1][i];
path[j][i] = grid[j][i] + path1;
}
}
return path[grid.size()-1][grid[0].size()-1];
}

};