走台阶问题(转)

一个楼梯有50个台阶，每一步可以走一个台阶，也可以走两个台阶，请问走完这个楼梯共有多少种方法？

举个例子，假设有3个台阶，则有三种走法：分别是，1-1-1, 1-2, 2-1。

分析

很简单的一道题，学过组合数学的人很快就能想到，这是一个递推关系。假设走完k个台阶有f(k)种走法。

k = 1时，f(k) = 1k = 2时，f(k) = 2k = n时，第一步走一个台阶，剩n-1个台阶，有f(n - 1)种走法。第一步走两个台阶，剩n-2个台阶，有f(n - 2)种走法。所以共有f(n - 1) + f(n - 2)种走法。

于是有如下公式

代码

分析一下，假设铺完长度为n的地面有f(n)种方法，如果第一块地砖竖起来铺，还剩下长度为n-1的地面，有f(n-1)种方法。如下图。

如果第一块地转横着铺，那么还剩下长度为n-2的地面，有f(n-2)种铺法。如下图。

所以这道题与上面的题解法完全一样。不同的题目，相同的模型而已。

自然数拆分

给定一个自然数n，将其拆分为若干个自然数字之和，请问有多少种方法？举个例子，n=4时，可以拆分为1-1-1-1，1-1-2，1-3，2-2。

这题和上面的题很像，不过上面的问题是排列问题，而这题是组合问题，比如n=4时，1-1-2，1-2-1，2-1-1这三种只能算一个拆分。在上面的基础上，去掉重复的组合即可。

?

?

作者：zdd出处：http://www.cnblogs.com/graphics/