HDU2067动态规划与卡特兰数的应用分析

Problem Description
小兔的叔叔从外面旅游回来给她带来了一个礼物&＃xff0c;小兔高兴地跑回自己的房间&＃xff0c;拆开一看是一个棋盘&＃xff0c;小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0&＃xff0c;0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)&＃xff0c;这样的路径数有多少?小兔想了很长时间都没想出来&＃xff0c;现在想请你帮助小兔解决这个问题&＃xff0c;对于你来说应该不难吧!

Input
每次输入一个数n(1<&＃61;n<&＃61;35)&＃xff0c;当n等于&＃xff0d;1时结束输入。

Output
对于每个输入数据输出路径数&＃xff0c;具体格式看Sample。

Sample Input
1
3
12
-1

Sample Output
1 1 2
2 3 10
3 12 416024

DP题解&＃xff1a;

参考http://blog.sina.com.cn/s/blog_a16dd6d101014q6x.html
假设是8*8的矩阵

箭头方向表示从该格子下一步能去的格子。因为不能穿越对角线&＃xff0c;所有对角线上的格子只有进去的箭头&＃xff0c;没有出来的箭头。
不难推出状态转移方程
if(i&＃61;&＃61;j)
dp[i][j]&＃61;dp[i][j-1]
else
dp[i][j]&＃61;dp[i-1][j]&＃43;dp[i][j-1]
我们只需要求对角线一半的路径数&＃xff0c;因为它是关于对角线对称的&＃xff0c;不难发现0列0行的路径数是1&＃xff0c;注意初始化

代码&＃xff1a;

#include
#include
#include
using namespace std;
typedef long long LL;
LL f[45][45];int main()
{for(int i&＃61;0;i<40;i&＃43;&＃43;)f[i][0]&＃61;1;for(int i&＃61;0;i<40;i&＃43;&＃43;){for(int j&＃61;1;j<40;j&＃43;&＃43;){if(i&＃61;&＃61;j)f[i][j]&＃61;f[i][j-1];elsef[i][j]&＃61;f[i][j-1]&＃43;f[i-1][j];}}int n;int ks&＃61;1;while(cin>>n&&n!&＃61;-1){//cout<printf("%d %d %lld\n",ks&＃43;&＃43;,n,2*f[n][n]);}return 0;
}


题解&＃xff1a;

参考http://blog.csdn.net/hackbuteer1/article/details/7450250
此题属于卡特兰数列经典之一

代码&＃xff1a;

#include
using namespace std;
int main(){long long Cata[40];Cata[0]&＃61;Cata[1]&＃61;1;for(int i&＃61;2;i<&＃61;35;i&＃43;&＃43;){for(int j&＃61;0;j*Cata[i-j-1];}// printf("%lld\n",Cata[i]);}int kase&＃61;0,n;while(scanf("%d",&n)!&＃61;EOF && n>0){printf("%d %d %lld\n",&＃43;&＃43;kase,n,2*Cata[n]);}return 0;
}