九度OJ 题目1529：棋盘寻宝 （简单DP）

题目：http://ac.jobdu.com/problem.php?pid=1529

简单DP：

#include<iostream>#include<cstring>#include<cstdlib>#include<fstream>using namespace std;int dp[9][9];int num[9][9];int main(){//ifstream fin;//fin.open("input.txt");while(cin>>num[1][1]){for(int i=1;i<=8;i++){for(int j=1;j<=8;j++){if(i==1 && j==1) continue;cin>>num[i][j];}}memset(dp,0,sizeof(dp));dp[1][1]=num[1][1];for(int i=2;i<=8;i++){dp[i][1]=num[i][1]+dp[i-1][1];}for(int j=2;j<=8;j++){dp[1][j]=dp[1][j-1]+num[1][j];}for(int i=2;i<=8;i++){for(int j=2;j<=8;j++){dp[i][j]=max(dp[i][j-1],dp[i-1][j])+num[i][j];}}cout<<dp[8][8]<<endl;}return 0;}