Joyce' Blog
0%

小兔的棋盘

发表于 更新于

题目描述

棋盘，从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?

题解

==卡特兰数==

动态规划求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int chessboard(int n)
{
	if (n < 1)return 0;
	int** dp = new int*[n];
	for (int i = 0; i < n; i++)
		dp[i] = new int[n];
	for (int i = 0; i < n; i++)
		dp[0][i] = 1;
	dp[1][1] = 1;
	for (int i = 1; i < n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			if (i == j)
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
		}
	}
	return dp[n - 1][n - 1]*2;
}

还没有测试，抓紧时间看面经吧。