蓝桥杯-拿金币

资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

　　有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。

输入格式

　　第一行输入一个正整数n。
　　以下n行描述该方格。金币数保证是不超过1000的正整数。

输出格式

　　最多能拿金币数量。

样例输入

3
1 3 3
2 2 2
3 1 2

样例输出

11

数据规模和约定

　　n<=1000

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<vector<int> > v(n,vector<int>(n));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>v[i][j];
		}
	}
	int res=-1;
	vector<vector<int> > v1(n,vector<int>(n));
	v1[0][0]=v[0][0];
	for(int j=1;j<n;j++){
		v1[0][j]=v1[0][j-1]+v[0][j];//第一行只能是从左边来的
	}
	for(int i=1;i<n;i++){
		v1[i][0]=v1[i-1][0]+v[i][0];//第一列只能是从上一行来的
	}
	for(int i=1;i<n;i++){
		
		for(int j=1;j<n;j++){
			v1[i][j]=max(v1[i-1][j],v1[i][j-1])+v[i][j];//走到每个位置时的最大金币数等于它左边或上面的金币数的最大值加上这个位置的金币数
			if(v1[i][j]>res)
			res=v1[i][j];//记录最大值
		}
		
	} 	
	//cout<<v1[0][2]<<endl; 
	cout<<res<<endl;
	
}