跳台阶问题(变态跳台阶)的解法

66 阅读 0 评论 44 点赞

我是靠谱客的博主傲娇荔枝，这篇文章主要介绍跳台阶问题(变态跳台阶)的解法，现在分享给大家，希望可以做个参考。

一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法，并分析算法的时间复杂度。

我们把n级台阶时的跳法看成是n的函数，记为f(n)。当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)；另外一种选择是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此n级台阶时的不同跳法的总数f(n)=f(n-1)+(f-2)。

我们把上面的分析用一个公式总结如下：

这个就是我们熟悉的Fibonacci序列

// 三种解法

//递归解法
int solution1(int n)
{
    if(n == 0)
        return 0; 
    if(n == 1) 
        return 1;
    else 
        return solution1(n-1) + solution1(n-2);
}

//非递归解法
int solution2(int n)
{
    if(n == 0)
        return 0;
    int f[100], i;
    f[0] = 1;
    f[1] = 1;
    for(i = 2; i <= n; ++i)
       f[i] = f[i - 1] +