博客

int GetMaxValue(vector<vector<int> > &arr)
{
	if(arr.size() == 0||arr[0].size() == 0)
		return 0;
	int m = arr.size();
	int n = arr[0].size();
	vector<vector<int> > dp(m,vector<int>(n));
	
	dp[0][0] = arr[0][0];//动态规划问题中这类问题经常出现
	
	for(int i = 1;i < m;i++)
	{
		dp[i][0] = arr[i][0];
	}
	for(int j = 1;j < n;j++)
	{
		dp[0][j] = arr[0][j];
	}
	
	for(int i = 1;i < m;i++)
		for(int j = 1;j < n;j++)
		{
			dp[i][j] = max(dp[i][j-1],dp[i-1][j])+arr[i][j];
		}
	return dp[m-1][n-1];
}