题目链接：

https://www.acwing.com/problem/content/1029/

分析：

f[k][i][j] 两次都走了k步，第一次走到了[i][k - i] , 第二次走到了 [j][k - j];

同时可以通过第k - 1步推出 第k步的状态

状态1：  第一次 向下走一步，  第二次 也向下走一步.  f[k - 1][i - 1][j - 1];
状态2：  第一次 向下走一步，  第二次 向右走一步， f[k - 1][i - 1][j];
状态3：  第一次 向右走一步，  第二次 向下走一步,  f[k - 1][i][j - 1];
状态4：  第一次 向右走一步，  第二次 向右走一步， f[k - 1][i][j];

求出这四个之中的最大值temp。

(1.) 最后 当 i == j的时候。 第一次走到[i][k - i] :    temp = temp + w[i][k - i];
第二次走的时候[i][k - i]被置为0 ：  所以第二次 temp = temp + 0;

(2.) 最后 当 i != j的时候。 第一次走到[i][k - i] :    temp = temp + w[i][k - i];
第二次走的时候[j][k - j]被置为0 ：  所以第二次 temp = temp +w[j][k - j];

代码实现：

# include <iostream>
using namespace std;

const int N = 15;

int w[N][N];
int f[N + N][N][N];

int main()
{
    int n;
    scanf("%d",&n);
    int a,b,c;
    while(~scanf("%d %d %d",&a,&b,&c) && (a || b || c))
    {
        w[a][b] = c;
    }

    for(int k = 1 ; k <= n + n ; k++)
    {
        for(int i = 1;  i <= min(n,k) ; i++)  //为什么取min呢？因为k - i或者k - j 中要防止 i 或者 j > k的情况出现
        {
            for(int j = 1 ; j <= min(n,k) ; j++)
            {   
                f[k][i][j] = max(f[k][i][j],f[k - 1][i - 1][j - 1]);
                f[k][i][j] = max(f[k][i][j],f[k - 1][i - 1][j]);
                f[k][i][j] = max(f[k][i][j],f[k - 1][i][j - 1]);
                f[k][i][j] = max(f[k][i][j],f[k - 1][i][j]);
                if(i == j)
                {
                    f[k][i][j] += w[i][k - i];
                }
                else
                {
                    f[k][i][j] = f[k][i][j] + w[i][k - i] + w[j][k - j];
                }
            }
        }
    }
    printf("%d\n",f[n + n][n][n]);
    return 0;
}