70. 爬楼梯

image.png

递归解法

  1. public class Solution {
  3.     // 用于缓存计算结果，防止重复计算
  4.     HashMap<Integer, Integer> map = new HashMap<>();
  6.     //设跳上 n 级台阶一共有 f(n) 种跳法，则 f(n) = f(n - 1) + f(n - 2)
  7.     // 而 f(0) = 1, f(1) = 1
  8.     public int climbStairs(int n) {
  9.         if (n <= 3) return n;
  10.         // 如果不存在，计算并缓存
  11.         if (!map.containsKey(n - 1)) {
  12.             map.put(n - 1, climbStairs(n - 1));
  13.         }
  14.         if (!map.containsKey(n - 2)) {
  15.             map.put(n - 2, climbStairs(n - 2));
  16.         }
  17.         // 直接取缓存结果相加返回
  18.         return map.get(n - 1) + map.get(n - 2);
  19.     }
  20. }