首先看一个经典问题：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶，你每次可以爬 1阶或者 2阶，问你有多少种方法爬到楼顶

示例：
输入：2，输出：2
输入：3，输出：3
思路分析：
这道题目只求到达目的地解法个数，不需要求具体的解决路径

递归+记忆化搜索

首先用递归 + 记忆化搜索解决，记忆化搜索主要用来解决递归项的重复计算问题

  1. const cache = [] // 记忆化搜索就是在递归里加缓存，自顶向下
  2. const climbStairs = function(n){
  3.   // 递归先写边界条件
  4.   if(n===1){
  5.     return 1
  6.   }
  7.   if(n===2){
  8.     return 2
  9.   }
  10.   if(!cache[n]){
  11.        cache[n] = climbStairs(n-1) + climbStairs(n-2) // 递归式
  12.   }
  13.   return cahch[n]
  14. }

递归式cache[n] = climbStairs(n-1) + climbStairs(n-2)是自顶向下思考的，从最后的结果倒着往前推。

动态规划

动态规划与递归思路相反，是自底向上的思考，通过状态转移方程进行遍历从底部计算到顶部
这道题的状态转移方程和递归式一样：f(n) = f(n-1) + f(n-2)

  1. const climb = function(n){
  2.     const cache = []
  3.   cache[1] = 1
  4.   cache[2] = 2
  5.   for(let i=3; i<= n;i++){
  6.     cache[n] = cache[n-1] + cache[n-2]
  7.   }
  8.   return cache[n]
  9. }

由上我们可以看出，动态规划问题有两个关键特征：

  1. 整体的最优解包含着子问题最优解
  2. 子问题的最优解会被多次计算，需要缓存来提高性能