HDU2067小兔的棋盘（递推，动态规划）

解题思路：类似于动态规划的递推题，题目有个限制，不能超过图的主对角线。我们求出其中一半到达终点的路径数，结果*2就为最终解。设状态:dp[i][j]为起点到达坐标(i,j)的路径数，状态转移方程:dp[i][j]=dp[i-1][j]+dp[i][j-1],注意对角线上的点只能从其中一个点过来，看你是算哪一边的。然后边界的和终点同一行的点要注意初始化处理。

AC代码如下：

#include<stdio.h>
#include<string.h>

long long dp[50][50];

int main()
{
    int i,n,j,t=1;
    for(i=0;i<=36;i++)
        dp[0][i]=1;
    for(i=1;i<=36;i++)
    {
        dp[i][i]=dp[i-1][i];
        for(j=i+1;j<=36;j++)
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
    }
    while(~scanf("%d",&n) && n!=-1)
        printf("%d %d %lld\n",t++,n,dp[n][n]*2);
	return 0;
}