题解:这其实也是斐波那契数列即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;
}