zstu 深入浅出学算法017——DFS——猴子爬山

Description

一个猴子在一座不超过30级的小山上爬山跳跃，猴子上山一步可跳1级或跳3级，试求上山有多少种不同的爬法

Input

多组测试数据，每组输入1个整数n,表示山的台阶数

Output

对于输入的整数n求出多少种爬法

Sample Input

30

Sample Output

58425

HINT

大意：经典DFS

#include<cstdio>
int n, tot;
void  dfs(int sum){
     if(sum ==  n){
         tot ++;
         return;
     }
     if(sum > n )
         return ;
     dfs(sum + 1);
     dfs(sum + 3);
}


int main()
{
    while(~scanf("%d",&n)){
         tot  = 0;
        dfs(0);
        printf("%d
",tot);
    }
    return 0;
}