LeetCode：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。思考：

/**
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。
 * 自顶向下求解思路：
 * 第10级：可以从第8级、第9级
 * 第9级：可以从第8级、第7级
 * ......
 *
 * 第2级：从第1级 2
 * 第1级：1
 *
 */

 最原始的求解方法【不推荐】 ：

// 普通递归求解，会有很多重复节点的计算过程，时间、空间复杂度都很高public static int stepNumWays(int step) {if (step == 1) {return 1;}if (step == 2){return 2;}return stepNumWays(step - 1) + stepNumWays(step - 2);}

带备忘录的递归求解，将一些重复计算节点放入集合保存，当下次计算的时候先访问集合是否存在该节点的计算结果，有就直接取出来，没有就计算求解。

优化方法：

/*** 带备忘录的递归求解* @param step* @return*/public static int stepNumWaysMemento(int step) {HashMap<Integer, Integer> map = new HashMap<>();if (step == 1) {map.put(1, 1);return 1;}if (step == 2){map.put(2, 2);return 2;}if ( map.containsKey(step)) {return map.get(step);} else {return stepNumWays(step - 1) + stepNumWays(step - 2);}}

从第一级到最后一级的顺序求解方法：

第1级=1

第2级=2

第3级=第1级 + 第2级

第4级=第3级 + 第2级

... ...

第10级 = 第9级 + 第8级

  /*** 顺序求解* @param step* @return*/public static int stepNumWaysStart(int step) {if (step <= 1) return 1;if (step == 2) return 2;int f1 = 1; //为什么初始值是1？因为1就是第一级台阶的到达方法int f2 = 2; //为什么初始值是2？因为2就是第一级台阶的到达方法int tmp = 0; //存结果用的临时对象，for (int i = 3; i <= step; i ++) { //3 是因为从第3级台阶开始的tmp = f1 + f2; // f3 = f2 + f1; f4 = f3 + f2 ...f1 = f2; //将位置大的与位置小的到达方法切换位置f2 = tmp; //将当前位置的值赋值}return tmp;}