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

  • 一个台阶总共有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] +

最后

以上就是傲娇荔枝最近收集整理的关于跳台阶问题(变态跳台阶)的解法的全部内容,更多相关跳台阶问题(变态跳台阶)内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(44)

评论列表共有 0 条评论

立即
投稿
返回
顶部