猴子爬山【Java】

猴子爬山【Java】

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

【输入描述】

输入只有一个整数N（0<N<=50）此阶梯有多少个阶梯

【输出描述】

输出有多少种跳跃方式（解决方案数）

【示例一】

• 输入

  50
  

• 输出

  122106097
  

【示例二】

• 输入

  3
  

• 输出

  2
  

【解题思路】

分析规律：

台阶个数，对应跳跃方案数
0个台阶，有1个方案。那就是不跳
1个台阶，有1个方案。跳1个台阶（1）
2个台阶，有1个方案。一个一个跳，跳两次（12）
3个台阶，有2个方案。一个一个跳，跳三次。以及一次性跳三阶（123,3）
4个台阶，有3个方案。（1234,14,34）
5个台阶，有4个方案。（12345,125,145,345）
6个台阶，有6个方案。（123456,1236,1256,1456,3456,36）
7个台阶，有9个方案。（123456789....369)

发现规律
1、台阶数n小于3时，都只有一种方案。
2、台阶数n大于等于3时，跳跃方案恰好等于(n-1)的台阶方案数+(n-3)的台阶方案数。例如：
台阶n=6的方案数等于5的台阶方案数+3的台阶方案数。

【代码】

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int num = input.nextInt();
        int count = cal(num);
        System.out.println(count);
    }

    private static int cal(int num) {
        if (num < 3) {
            return 1;
        }
        return cal(num - 1) + cal(num - 3);
    }

    //台阶数：0  1  2  3  4  5  6  7  8  9
    //方案数：1  1  1  2  3  4  6  9  13 19
}