题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。
方法:
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)。
$(".MathJax").remove();