【思特奇杯·云上蓝桥-算法集训营】第三周—爬楼梯

【思特奇杯·云上蓝桥-算法集训营】第三周—爬楼梯
题解:这其实也是斐波那契数列即fn=f(n-1)+f(n-2)。
思路:题目规定说每次只能跳一级或者两级,也就意味着如果我们要跳到第四级台阶,只能从第三级或者第二级台阶跳上去。因此我们可以简单转化为四级台阶的跳法等于三级台阶+二级台阶的跳法。即f(4)=f(3)+f(2),由此我们看到这就是一个斐波那契数问题:fn=f(n-1)+f(n-2)
【思特奇杯·云上蓝桥-算法集训营】第三周—爬楼梯
递归(递归算法在测试用例里是超时的,即无法通过测试)

#include<stdio.h>
int jump_step(int n)
{
	if(n==1)		return 1;
	else if(n==2)	return 2;
	else			return jump_step(n-1)+jump_step(n-2);
} 
int main()
{
	int n;
	int ret;
	printf("n=",n);
	scanf("%d",&n);
	ret=jump_step(n);
	printf("%d",ret);
	return 0;
}

【思特奇杯·云上蓝桥-算法集训营】第三周—爬楼梯
动态规划

#include<stdio.h>
int jump_step(int n)
{
	if(n<=2)    return n;
    int a=1;
    int b=2;
    int c=0;
    while(n>2)
    {  
        c=a+b;
        a=b;
        b=c;
        n--;
    }
    return c;
}
int main()
{
	int n;
	int ret;
	printf("n=",n);
	scanf("%d",&n);
	ret=jump_step(n);
	printf("%d",ret);
	return 0;
}

【思特奇杯·云上蓝桥-算法集训营】第三周—爬楼梯

上一篇:jump and mark


下一篇:一道算法题-跳跃游戏 II