题目地址:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1083
题目:
基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题
例如:3 * 3的方格。
1 3 3
2 1 3
2 2 1
能够获得的最大价值为:11。
Input
第1行:N,N为矩阵的大小。(2 <= N <= 500) 第2 - N + 1行:每行N个数,中间用空格隔开,对应格子中奖励的价值。(1 <= N[i] <= 10000)
Output
输出能够获得的最大价值。
Input示例
3 1 3 3 2 1 3 2 2 1
Output示例
11
思路:
动态规划。把大的状态用小的状态递推出来。比如3*3的矩阵,我们可以先算2*2的矩阵。
由(1,1)到(1,2)肯定就直接过去式最优解,(1,1)到(2,1)同理。
那么从(1,1)到(2,2)的最优解就可以从(1,2)和(2,1)中选一个大的了。
重复上面的操作,推广到n*n的矩阵,具体实现看代码把
代码:
#include<stdio.h>
int dp[550][550];
int n;
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&dp[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i==1&&j>1)//上边缘
dp[i][j]+=dp[i][j-1];
if(j==1&&i>1)//左边缘
dp[i][j]+=dp[i-1][j];
if(i>1&&j>1)//剩下的
{
dp[i][j]+=max(dp[i][j-1],dp[i-1][j]);
}
}
printf("%d\n",dp[n][n]);
}
return 0;
}