#include<iostream>
using namespace std;
int max(int x,int y)
{
if (x > y)
return x;
else
return y;
}
int main()
{
int n;
cin >> n;
int a[1000][1000];
int b[1000][1000];
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= n;j++)
{
cin >> a[i][j];
b[i][j] = 0;
}
}
for (int i = 0;i <= n;i++)
{
b[i][0] = 0;
b[0][i] = 0;
}
for (int x = 1;x <= n;x++)
{
for (int y = 1;y <= n;y++)
{
b[x][y] = max(b[x - 1][y], b[x][y - 1]) + a[x][y];
}
}
cout<<b[n][n];
return 0;
}

http://www.360doc.com/content/13/0601/00/8076359_289597587.shtml

http://www.51nod.com/tutorial/index.html#!tutorialId=1

动态规划1