1073: 矩阵取数I（动态规划）

题目描述

PIPI想要大家了解基本的动态规划，所以它不知道从哪弄来了一个n*m的矩阵，矩阵每个元素是一个整数，你现在在左上角（第一行第一列），你需要走到右下角（第n行，第m列），每次只能朝右或者下走到相邻的位置，不能走出矩阵。走过的数的总和作为你的得分，求最大的得分。 
怎么样，是不是很简单呢？ 

输入

多组输入。 
第一行为两个整数n,m（1<=n,m<=500) 
接下来n行，每行m个数字，每个数字都在int范围内。(￣▽￣)" 

输出

对于每组数据，输出最大和。

样例输入

4 4
1 2 3 4 
1 2 8 2
10 1 1 5
1 1 1 1

样例输出

22

【注】dp二维数组用long long型存储，否则不够.

 【思路】

#include<iostream>
using namespace std;
int main(void){
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF){
		//存储二维矩阵 
		int f[501][501];
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				scanf("%d",&f[i][j]);
			}
		}
		long long dp[501][501];
		//开始位置 
		dp[1][1]=f[1][1];
		//第一列初始化 
		for(int i=2;i<=n;i++){
			dp[i][1]=dp[i-1][1]+f[i][1];
		}
		//第一行初始化 
		for(int j=2;j<=m;j++){
			dp[1][j]=dp[1][j-1]+f[1][j];
		}
		//其他位置计算 
		for(int i=2;i<=n;i++){
			for(int j=2;j<=m;j++){
				dp[i][j]=max(dp[i][j-1],dp[i-1][j])+f[i][j];
			}
		}
	printf("%lld\n",dp[n][m]);
		 
	}
	return 0;
}