九度题目1529：棋盘寻宝

题目1529：棋盘寻宝
时间限制：1 秒
内存限制：128 兆
特殊判题：否
提交：682
解决：306
题目描述：
现在有一个8*8的棋盘，上面放着64个价值不等的礼物，每个小的棋盘上面放置一个礼物（礼物的价值大于0小于1000），一个人的初始位置在棋盘的左上角，每次他只能向下或向右移动一步，并拿走对应棋盘上的礼物，结束位置在棋盘的右下角，请设计一个算法使其能够获得最大价值的礼物。

输入：
输入包含多个测试用例，每个测试用例共有8行8列，第i行的第j列的数字代表了该处棋盘上的礼物的价值，每两个数之间用空格隔开。

输出：
对于每组测试用例，请输出你能够获得最大价值的礼物。

样例输入：
2 8 15 1 10 5 19 19
3 5 6 6 2 8 2 12
16 3 8 17 12 5 3 14
13 3 2 17 19 16 8 7
12 19 10 13 8 20 16 15
4 12 3 14 14 5 2 12
14 9 8 5 3 18 18 20
4 2 10 19 17 16 11 3

样例输出：
194

来源：
微策略2012年校园招聘笔试题

经典的dp：

#include<stdio.h>
#include<string.h>
int a[10][10],dp[10][10];
int max(int n,int m)
{return n>m?n:m;}
int main()
{
    int i,j,n,m;
    while(scanf("%d",&a[1][1])!=EOF)//防止超时（用while(1)一定会超时，以后慎用！！）
    {
       memset(dp,0,sizeof(dp));
       for(i=1;i<=8;i++)
       for(j=1;j<=8;j++)
       {
          if(i==1&&j==1)
          continue;
          scanf("%d",&a[i][j]);
       }
       dp[1][1]=a[1][1];
       for(i=1;i<=8;i++)
       for(j=1;j<=8;j++)
       {
          if(i==1&&j==1)
          continue;
          if(i==1)
          {
             dp[i][j]=dp[i][j-1]+a[i][j];
             continue;
          }    
          if(j==1)
          {
             dp[i][j]=dp[i-1][j]+a[i][j];
             continue;
          }      
          
          dp[i][j]=max(dp[i-1][j]+a[i][j],dp[i][j-1]+a[i][j]);    
       }
       
       printf("%d\n",dp[8][8]);
       memset(a,0,sizeof(a));
    }
    return 0;
}