一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
数据范围:![](https://www.nowcoder.com/equation?tex=1%20%5Cle%20n%20%5Cle%2020)
进阶:空间复杂度
, 时间复杂度
进阶:空间复杂度
//dp3 #include<stdio.h> #include<stdlib.h> int main(){ int n; while(scanf("%d",&n)!=EOF){ int *num=(int *)malloc(sizeof(int)*(n+1)); num[0]=0,num[1]=1,num[2]=2,num[3]=4; for(int i=4;i<=n;i++){ num[i]=1; for(int j=1;j<=i-1;j++) num[i]+=num[j]; } printf("%d\n",num[n]); } return 0; }