题目大意：小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?

解题思路：很明显的DP，dp[i][j]表示走到(i,j)的路径数。
              转移方程：dp[i][j]=dp[i-1][j]+dp[i][j-1](i!=j);
                            dp[i][j]=0(i=j);
              这里面要注意的是这里的(0,0)表示的是格子，而方程里面的(i,j)表示的是下格点
              所以事实上(n,n)换成格子表示是(n+1,n+1)
              而所有的对角线上的格点也是来源于其左边和上面的格点所以ans=dp[n+1][n]+dp[n][n+1]


代码：
 1#include <iostream>
 2#include <cstdio>
 3#include <cstring>
 4#include <cmath>
 5
 6using namespace std;
 7
 8int m,n,k;
 9long long dp[40][40];
10
11int main()
12{   dp[0][0]=0;
13    for (int i=0; i<=37; i++)
14      { dp[0][i]=1; dp[i][0]=1;
15      }
16    for(int i=1; i<=37; i++)
17        for(int j=1; j<=37; j++)
18            if(i != j)
19                dp[i][j] = dp[i-1][j] + dp[i][j-1];
20
21            else
22                dp[i][j] = 0;
23    k=1;
24    while(cin >> n)
25        {if (n==-1) break;
26        cout <<k <<" "<<n<< " " <<dp[n+1][n]+dp[n][n+1] << endl; k++;}
27
28    return 0;
29}
30


其实勒，这道题是由于数据量比较小，所以可以使用DP+long long来解决，但是其本质上还是属于一个排列组合问题，如果数据量变大的话，需要用到大数来解决。