上楼梯问题 – Advanced

上楼梯问题 – Advanced

Alice想登上N阶的楼梯,每一步Alice可以上一阶也可以上两阶,问登上N阶楼梯总共有多少种方法。稍有编程基础就知道这符合Fibonacci数列,因为Alice上N阶楼梯的走法F(n) 等于它走N-1阶的方案与N-2阶的方案之和,即F(n) = F(n-1) + F(n-2)。

现在Bob也想上N阶的楼梯,每一步Bob可以上一阶、两阶、三阶、…,M阶,这时登上N阶楼梯共有多少种方法。类似的,有\( F(n) = \sum_{i=1}^{M} F(n-i) \)。Alice的走法就是Bob的走法当M=2的情形。

接下来才是要重点讨论的内容:Cindy要登上N阶的楼梯,每一步能上1,2,…,M阶,但是Cindy这一步跨的阶数不能与上一步相同,试问恰好上到第N阶有多少种方案。

如果M为1,那么N大于1时Cindy永远无法登上。M若为2,则Cindy只能[1,2,1,2,…]或[2,1,2,1,…],如果N是3的正整数倍,那么Cindy就有两种方案,否则就只有1种方案。M若是大于2的情况,我们就需要用一个方法保存上一步的走法。用数组d[i][k]表示一个状态,表示Cindy走了k步到第i阶,那么在走k步之前的状态是d[i-k][...],要求相邻两步不能相同,也就是d[i-k][j]的所有j不为k的情况,即 \( d[i][k] = \sum_{j=1,j \neq k}^{M} d[i-k][j] \).要计算Cindy到第i阶的方案数,就是把所有的可能的k累加:\( \sum_{k=1}^{M} d[i][k] \)。在写程序实现时要注意阶梯数小于M与大于等于M时的d[i][k]的计算有细微区别:

int dp(int M,int N)
{
	int i,j,k;
	for(i=1;i<=M;i++)
	{
		d[i][i]=1;
		for(k=1;k<i;k++)
		{
		for(j=1;j<i;j++)
		{
			if(j!=k)
			{
				d[i][k] += d[i-k][j];
			}
		}}
	}
	for(i=M+1;i<=N;i++)
	{
		for(k=1;k<=M;k++)
		{
		d[i][k] = 0;
		for(j = 1;j<=M;j++)
		{
			if(i>k && j!=k)
			{
				d[i][k] += d[i-k][j];
			}
		}
		}
	}
	int res=0;
	for(int i=1;i<=M;i++)
	{
		res+=d[N][i];
	}
	return res;
}

Dave想登上一个有N阶的楼梯,每一步可以走1,2,..,M阶,但是Dave跨过的阶数不能与之前的两步相同,问恰好上到第N阶有多少种方案。

// TODO 这有点难

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注