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 这有点难