动态规划也是算法设计思想。
动态规划也是把大问题分解成小问题，但这些小问题之间不是独立的，而是相互关联的小问题。这就是动态规划和分治的核心区别。
最能说明动态规划的简单例子就是：斐波那契数列
0、1、1、2、3、5、8、13、21、34……
这个数列的第n项数字（n >= 2）就可以归纳为：
F(n) = F(n - 1) + F(n - 2)
子问题的独立性，是动态规划和分而治之的区别，可以体会斐波那契和二叉树翻转这两个代表性的例子。

leetCode.70 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。 示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

这个题问爬到n阶的方法个数，爬到n，就相当于，爬到n-1阶 + 1 或者 爬到n - 2阶 + 2。那么这个问题就转换成了求n-1阶，和求n-2阶的方法数量… … F(n) = F(n - 1) + F(n - 2)。
那么可以用动态规划了。

  2. var climbStairs = function(n) {
  3.     if(n < 2) return 1;
  4.     const ways = [1, 1];
  5.     for (i = 2; i <= n; i += 1) {
  6.         ways[i] = ways[i - 1] + ways[i - 2] 
  7.     }
  8.     return ways[n]
  9. };

leetCode.198 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1： 输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2： 输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

子问题归纳为：当小偷偷窃第k个房屋的时候，他能获得的最大收益
f(k) = max( f(k -2) + k, f(k -1) )

  1. var rob = function(nums) {
  2.     if(nums.length === 0) return 0;
  3.     const robmax = [0, nums[0]];
  4.     for(k = 2; k < nums.length; k += 1 ) {
  5.         robmax[k] = Math.max(
  6.             robmax[k - 2] + nums[k -1 ], 
  7.             robmax[k - 1] 
  8.         );
  9.     }
  10.     return robmax[robmax.length - 1];
  11. };