收藏
关注第1行：N，N为矩阵的大小。(2 <= N <= 500) 第2 - N + 1行：每行N个数，中间用空格隔开，对应格子中奖励的价值。（1 <= N[i] <= 10000)
输出能够获得的最大价值。
3 1 3 3 2 1 3 2 2 1
11
#include<bits/stdc++.h>
#define maxn 500+10
using namespace std;
int a[maxn][maxn];
int dp[maxn][maxn];
int i,j;
int n;
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(dp, 0, sizeof(dp));
memset(a, 0,sizeof(a));
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j];
}
}
printf("%d\n",dp[n][n]);
}
return 0;
}
原文：http://www.cnblogs.com/ruruozhenhao/p/7486328.html