题目大意:小兔的叔叔从外面旅游回来给她带来了一个礼物,小兔高兴地跑回自己的房间,拆开一看是一个棋盘,小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(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==-1break;
26        cout <<<<" "<<n<< " " <<dp[n+1][n]+dp[n][n+1<< endl; k++;}

27
28    return 0;
29}

30


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