动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。

动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归，自底向上就是递推。

使用动态规划解决的问题有个明显的特点，一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量。

以上是一段对动态规划不知所云的描述，我第一次看到的时候，一度怀疑这是否是人类所写下的语句。DP无论是在IO还是各大招聘中都是举足轻重的，虽然这些和我毫不相关，但锻炼一下思维肯定不是一件坏事。

0. DP

动态规划简单说就是将一个大问题拆分成若干小问题，并通过重复调用这些小问题中获得的结果得到最后的答案。例如入门的爬楼梯问题：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

对于上述问题，如果为1时，显然只有1种解法，为2时，显然也只有2种解法。当为3时，你可能不能立马得出答案为3。但不难发现，只需要分别在第一阶和第二阶的时候分别向上爬2和1阶就可以达到第三阶，也就是, 将这个公式推广开就可以得到:

即我们只需要记住前两个“台阶”的结果，即可得到当前台阶的结果。

const solution = (n) => {
  let prev = 0, curr = 1
  if (n===1) {
    return 1
  }
  
  for (let i=0; i<n-1; i++) {
    [curr, prev] = [curr+prev, curr];
  }
  
  return curr
}

复杂度为