需求：
一天一只顽猴想去从山脚爬到山顶，途中经过一个有个N个台阶的阶梯，但是这猴子有一个习惯：每一次只能跳1步或跳3步，试问猴子通过这个阶梯有多少种不同的跳跃方式？
输入描述
输入只有一个整数N（0 输出描述
输出有多少种跳跃方式（解决方案数）。
输入
3
输出
2
输入
50
输出
122106097
分析:
上山最后一步到达第50级台阶，完成上山，共有f（50）种不同的爬法，
到第50级之前位于哪一级呢？无非是位于第49级（上跳1级即到），有f（49）种；
或位于第48级（上跳3级即到），有f（48）种，于是：
f（50）=f（49）+f（47）
f（49）= f（48）+f（46）
f（48）= f（47）+f（45）
依次类推
以此类推，一般地有递推关系：
f（n）=f（n-1）+f（n-3） （n>3）
初始条件：
f（1）=1，即1=1；
f（2）=1，即2=1+1（注意：跳法中不允许直接跳2级）；
f（3）=2，即3=1+1+1，3=3；
故此递推设计比较简单，时间复杂度为O（n）
编码：
public class TestDump { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); System.out.print("请输入阶梯数："); int num=scanner.nextInt(); System.out.println(showF(num)); } public static long showF(int n) { if (n == 1 || n == 2) { return 1; } if (n == 3) { return 2; } return showF(n - 1) + showF(n - 3); }}
效果：
来源地址：https://blog.csdn.net/hlx20080808/article/details/132981013
0