- 一个台阶总共有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] +
最后
以上就是傲娇荔枝最近收集整理的关于跳台阶问题(变态跳台阶)的解法的全部内容,更多相关跳台阶问题(变态跳台阶)内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复