使用带缓存结构的递归方法解决“青蛙跳台阶”问题

题目：青蛙跳台阶
描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：众所周知，递归这种思想存在重复计算的缺陷，上篇文章我们用循环(迭代）法优化了递归算法，这次我们给递归加上缓存，同样能解决重复计算的问题。站长以为，这种方案更加符合人们思考问题的方式，也更好理解。

优化方式一：循环(迭代）法，参考：https://www.codernav.com/2806.html
优化方式二：带缓存结构的递归法
优化方案三：动态规划法，参考：https://www.codernav.com/2802.html
操作步骤：
1、定义缓存结构
2、递归方法中，先从缓存中读取数据
3、如果缓存中没有读取到数据，则使用递归算法取值
4、将递归算法取到的值放入缓存中

package od;

import java.util.HashMap;
import java.util.Map;

/**
 * 青蛙跳台阶（带缓存方案）
 * 问题描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 * 原文地址：https://www.codernav.com/2809.html
 * 更多算法详解：https://www.codernav.com
 */
public class OdTest14 {
    public static void main(String[] args) {
        // 1.定义缓存结构
        Map<Integer, Integer> cacheMap = new HashMap<>();
        int way = f(10, cacheMap);
        // 输出：89
        System.out.println(way);
    }

    private static int f(int n, Map<Integer, Integer> cacheMap) {
        if (n <= 2) {
            cacheMap.put(n, n);
            return n;
        }
        // 2.先从缓存中查
        if (cacheMap.containsKey(n)) {
            return cacheMap.get(n);
        }
        // 3.缓存中没有，使用递归计算
        int way = f(n - 1, cacheMap) + f(n - 2, cacheMap);
        // 4.加入缓存
        cacheMap.put(n, way);
        return way;
    }
}