动态规划并不是一种特殊算法。而是对解最优化问题的一种途径、一种方法。并没有一种标准的数学表达式和明确的解题方法，由于各种问题性质不同，确定最优解的条件也不相同。
动态规划要找到递推公式

动态规划的思路就是把大问题一直拆分，拆分到原子级别。也就是最简单的问题，然后逐步推导出大问题的结论

爬楼梯问题，
现在有一个10层的楼梯，每次只能上1个或者2个楼梯，有多少种方法爬到第10层

分析问题
第一个台阶，只有一种方法, 1
第二个台阶，有两种方法，1 -> 1, 2
第三个台阶，有三种方法， 1->1 -> 1, 1->2 ， 2->1
第四个台阶，有五种方法， 1->1->1->1->1, 1->2->1->1, 1-2->2, 2->1->2, 2->2->1
….
爬第n个台阶，等于 第n-1的台阶的方法 + 第n-2台阶的方法

  1. // 递归
  2. function climbStairs(n) {
  3.     if (n == 0 || n == 1 || n == 2) {
  4.       return n
  5.   }
  6.   return climbStairs(n-1) + climbStairs(n-2)
  7. }
  9. // 循环
  10. function climbStairs(n) {
  11.     if (n == 0 || n == 1 || n == 2) {
  12.       return n
  13.   }
  14.   let a = 1;
  15.   let b = 2;
  16.   for (let i = 3; i <=n; i++) {
  17.    [a, b] = [b, a + b]
  18.   }
  19.   return b;
  20. }

练习题

两数之和。
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

  1. /**
  2. 给定 nums = [2, 7, 11, 15], target = 9
  4. 因为 nums[0] + nums[1] = 2 + 7 = 9
  5. 所以返回 [0, 1]
  7. */
  9. function twoSum(nums, target) {
  10.     let map = new Map;
  11.   for (let i = 0; i < nums.length; i++) {
  12.       if (map.has(target - nums[i])) {
  13.       return [map.get(target - nums[i]), i]
  14.     } else {
  15.       map.set(nums[i], i)
  16.     }
  17.   }
  18. }
  19. let nums = [2, 7, 11, 15], target = 9;
  20. console.log(twoSum(nums, target))