题目来源“数据结构与算法面试题80道”。
问题分析：假设fleft ( n right ) 为跳台阶的总跳法，当n=1 时，fleft ( n right )=1 ；当n=2 时，fleft ( n right )=2 ；当n=3 时，如果先跳1级台阶，有fleft ( n-1 right )=fleft ( 2 right ) 种方法，如果先跳2级台阶，有fleft ( n-2 right )=fleft ( 1 right ) 种方法，依次类推，可以得到下面的递推公式：
方法：
代码语言：javascript复制int get_kind(int n){
if (n <= 0) return 0;
int result;
int *cal = (int *)malloc(sizeof(int) * n);
for (int i = 0; i < n; i ){
if ((i 1) == 1) cal[i] = 1;
else if ((i 1) == 2) cal[i] = 2;
else {
cal[i] = cal[i-1] cal[i-2];
}
}
result = cal[n-1];
free(cal);
return result;
}时间复杂度为O(n)。
