网上看到说这题还能用卡特兰数解，有兴趣的可以取搜搜。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2067

题意：

给出一个矩阵，不能穿越对角线，但可以触碰到，问从a[1][1] 走到 a[n][n]又多少种方法。

分析：

我们首先考虑a[n][n]，a[n][n]可以从a[n-1][n]和a[n][n-1]两种状态得到，但是因为不能穿越对角线，所以我们只考虑一半的情况，然后根据对称性来得到最终的结果。

对角线上的点那么a[i][i]就只能从a[i][i-1]得到这是一种特殊情况, dp[i][i] = d[i][i-1]

其他点则可以是 dp[i][j] = dp[i][j-1] + dp[i-1][j]

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 40;
typedef long long LL;

LL a[N][N];

int main()
{
    int n;
    int cnt = 1;
    while(scanf("%d", &n), n != -1)
    {
        for(int i=0; i<N; i++)
        {
            a[i][0] = 1;    // 棋盘边上的点只有一条路径
            a[0][i] = 1;
        }
        for(int i=1; i<N; i++)
        {
            for(int j=1; j<i; j++)    // 只考虑对角线一边的情况
            {
                a[i][j] = a[i-1][j] + a[i][j-1];
            }
            a[i][i] = a[i][i-1];    // 对角线上的点只能从它的下方得到
        }
        // a[n][n] = a[n][n-1];
        
        // 根据对称性，最后的结果×2即可
        printf("%d %d %lld\n", cnt++, n, 2 * a[n][n]);


    }


    return 0;
}