[数据结构与算法]题目5 猴子爬山（递归）

一天一只顽猴想要从山脚爬到山顶
? 途中经过一个有n个台阶的阶梯，但是这个猴子有个习惯，每一次只跳1步或3步
? 试问？猴子通过这个阶梯有多少种不同的跳跃方式

? 输入描述：
?? ?输入只有一个这个数n ? ?0<n<50
?? ?此阶梯有多个台阶
? 输出描述：
?? ?有多少种跳跃方式

? 实例:
? ?输入
?? ? 50
? ?输出
?? ? ?122106097

? ?输入
?? ? ?3
? ?输出
?? ? ?2

int count = 0;
/* 1.深度优先搜索 */
int dfs(int cur, int n)
{
    if (cur == n) {
        count++;
    }

	if (cur >= n) {
        return 0;
	}
	dfs(cur + 1, n);
	dfs(cur + 3, n);
}

/* 2.动态规划 */
int fun(int n)
{
    if (n == 1 || n == 2) {
		return 1;
    }

    if (n == 3) {
		return 2;
   	}
    if (n > 3) {
		count = fun(n - 1) + fun(n -3);
    }
	return count;
}

/* 3.循环 */
int search(int n)
{
    int f1 = 1;
    int f2 = 1;
    int f3 = 2;
    int f4 = n == 1 || n == 2 ? 1 : 2;
    for (int i = 4; i <= n; i++) {
        f4 = f3 + f1;
        f1 = f2;
        f2 = f3;
        f3 = f4;
    }

    printf("f4=%d\n", f4);
	return f4;
}