You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?Note : Given n will be a positive integer.
本题对应于《剑指offer》P75的跳台阶问题：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
首先我们考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。
接着我们再来讨论一般的情况。把n级台阶时的跳法看成是n的函数f(n)。当n>2时，第一次跳的时候有两种不同的选择：
- 第一次只跳1级，此时跳上n级台阶的跳法数目等于后面剩下的n-1级台阶的跳法数目，即f(n-1)
- 第一次跳2级，此时跳上n级台阶的跳法数目等于后面剩下的n-2级台阶的跳法数目，即f(n-2)
因此n级台阶的不同跳法的总数 f(n) = f(n-1) + f(n-2)
上面的分析过程，我们用到了动态规划的方法，找到了状态转移方程，不难看出这实际上就是一个类斐波那契数列，只是初始条件与传统的斐波那契数列略有不同，这里f(2)=2。
关于斐波那契数列，我在之前的文章中已经详细分析了这类问题的三种计算机解法：自上而下的递归实现太耗时，转化为特征矩阵的乘方又太复杂，所以一般使用自底向上的迭代算法。
应用自底向上的迭代算法求解本题的源码如下，其时间复杂度为O(n)
public class Solution {
public int climbStairs(int n) {
if (n <= 2) {
return n;
}
int fibCurrent = 0, fibOneBack = 2, fibTwoBack = 1;
for (int i = 3; i <= n; i++) {
fibCurrent = fibOneBack + fibTwoBack;
fibTwoBack = fibOneBack;
fibOneBack = fibCurrent;
}
return fibCurrent;
}
}
系统准备一个函数，是常数项时间复杂度比较大的事情，而且系统递归栈的大小也是有限的，所以工程上的代码，很少使用递归。对于一种算法的递归版本，往往可以通过自己维护一个栈或者迭代的方式，将其改写成非递归版本进行优化。
《剑指offer》上还对本题进行了如下扩展
一只青蛙一次可以跳上1级台阶，也可以跳上2 级，……，也可以跳上n级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？
首先我们仍然考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。
接着我们再来讨论一般的情况。把n级台阶时的跳法看成是n的函数f(n)。当n>2时，第一次跳的时候有n种不同的选择：
- 第一次只跳1级，此时跳上n级台阶的跳法数目等于后面剩下的n-1级台阶的跳法数目，即f(n-1)；
- 第一次跳2级，此时跳上n级台阶的跳法数目等于后面剩下的n-2级台阶的跳法数目，即f(n-2)；
- 第一次跳3级，此时跳上n级台阶的跳法数目等于后面剩下的n-3级台阶的跳法数目，即f(n-3)；
- ......；
- 第一次跳n-1级，此时跳上n级台阶的跳法数目等于后面仅剩的1级台阶的跳法数目，即f(1)；
- 从初始位置直接跳n级，这也对应了一种跳法
综上所述，n级台阶的不同跳法的总数 f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(1) + 1
把n-1带入上面的递推式得 f(n-1) = f(n-2) + f(n-3) + ... + f(1) + 1
所以最终的递推式为 f(n) = 2 * f(n-1)
应用自底向上的迭代算法求解本题的源码如下：
public class Solution {
public int climbStairs(int n) {
int result = 1;
if (n == 1) {
return result;
}
for (int i = 2; i <= n; i++) {
result *= 2;
}
return result;
}
}
网友评论