题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2686
题意： 一个n*n矩阵（内为小于100的正整数），求从左上角走到右下角，再从右下角走到左上角，每格只能走一次，两线路不相交，将走过格子内的数目相加，求最大值。
思路：可转化为两条线路同时从左上角出发到右下角。
如图，黄框内的数字为第几步能到达该框。
令dp[k][i][j]表示第k步走到的两个点(i，k-i)、(j，k-j) （i不等于j，因为不能交叉）
则有状态转移方程dp[k][i][j] = max(dp[k-1][i-1][j-1]，dp[k-1][i-1][j]，dp[k-1][i][j-1]，dp[k-1][i][j]) + a[i][k-i] + a[j][k-j]。
引用一个比较好的解释： http://www.cnblogs.com/183zyz/archive/2011/10/14/2212034.html
1 //状态dp[k][i][j] 第k步，该步走的是(i,k-i)、(j,k-j)
2 #include <cstdio>
3 #include <cstring>
4 #define N 35
5
6 int a[N][N], dp[2*N][N][N];
7 int max2(int x, int y)
8 {
9 return x > y ? x : y;
10 }
11
12 int main()
13 {
14 int n;
15 while(scanf("%d",&n)!=EOF)
16 {
17 for(int i=0; i<n; i++)
18 for(int j=0; j<n; j++)
19 scanf("%d",&a[i][j]);
20 if(n==1) printf("%d\n",a[0][0]);
21 else if(n==2) printf("%d\n",a[0][0]+a[1][0]+a[0][1]+a[1][1]);
22 else
23 {
24 memset(dp,0, sizeof(dp));
25 dp[1][0][1] = dp[1][1][0] = a[0][0] + a[1][0] + a[0][1];
26 for(int k=2; k<2*n-2; k++)
27 {
28 for(int i=0; i<n; i++)
29 {
30 for(int j=0; j<n; j++)
31 {
32 if(i==j || k-i>n-1 || k-j>n-1) continue;
33 if(i-1>=0 && j-1>=0) dp[k][i][j] = max2(dp[k][i][j], dp[k-1][i-1][j-1]+a[i][k-i]+a[j][k-j]);
34 if(i-1>=0 && k-1-j>=0 && (i-1)!=j) dp[k][i][j] = max2(dp[k][i][j], dp[k-1][i-1][j]+a[i][k-i]+a[j][k-j]);
35 if(k-1-i>=0 && j-1>=0 && i!=(j-1)) dp[k][i][j] = max2(dp[k][i][j], dp[k-1][i][j-1]+a[i][k-i]+a[j][k-j]);
36 if(k-1-i>=0 && k-1-j>=0) dp[k][i][j] = max2(dp[k][i][j], dp[k-1][i][j]+a[i][k-i]+a[j][k-j]);
37 }
38 }
39 }
40 int ans = max2(dp[2*n-3][n-2][n-1], dp[2*n-3][n-1][n-2]) + a[n-1][n-1];
41 printf("%d\n",ans);
42 }
43 }
44 return 0;
45 }
2 #include <cstdio>
3 #include <cstring>
4 #define N 35
5
6 int a[N][N], dp[2*N][N][N];
7 int max2(int x, int y)
8 {
9 return x > y ? x : y;
10 }
11
12 int main()
13 {
14 int n;
15 while(scanf("%d",&n)!=EOF)
16 {
17 for(int i=0; i<n; i++)
18 for(int j=0; j<n; j++)
19 scanf("%d",&a[i][j]);
20 if(n==1) printf("%d\n",a[0][0]);
21 else if(n==2) printf("%d\n",a[0][0]+a[1][0]+a[0][1]+a[1][1]);
22 else
23 {
24 memset(dp,0, sizeof(dp));
25 dp[1][0][1] = dp[1][1][0] = a[0][0] + a[1][0] + a[0][1];
26 for(int k=2; k<2*n-2; k++)
27 {
28 for(int i=0; i<n; i++)
29 {
30 for(int j=0; j<n; j++)
31 {
32 if(i==j || k-i>n-1 || k-j>n-1) continue;
33 if(i-1>=0 && j-1>=0) dp[k][i][j] = max2(dp[k][i][j], dp[k-1][i-1][j-1]+a[i][k-i]+a[j][k-j]);
34 if(i-1>=0 && k-1-j>=0 && (i-1)!=j) dp[k][i][j] = max2(dp[k][i][j], dp[k-1][i-1][j]+a[i][k-i]+a[j][k-j]);
35 if(k-1-i>=0 && j-1>=0 && i!=(j-1)) dp[k][i][j] = max2(dp[k][i][j], dp[k-1][i][j-1]+a[i][k-i]+a[j][k-j]);
36 if(k-1-i>=0 && k-1-j>=0) dp[k][i][j] = max2(dp[k][i][j], dp[k-1][i][j]+a[i][k-i]+a[j][k-j]);
37 }
38 }
39 }
40 int ans = max2(dp[2*n-3][n-2][n-1], dp[2*n-3][n-1][n-2]) + a[n-1][n-1];
41 printf("%d\n",ans);
42 }
43 }
44 return 0;
45 }