因为⼆叉 树是最容易培养框架思维的，⽽且⼤部分算法技巧，本质上都是树的遍历问
题
不要⼩看这⼏⾏破代码，⼏乎所有⼆
叉树的题⽬都是⼀套这个框架就出来了。

  1.  void traverse(TreeNode root) {
  2.         // 前序遍历
  3.        traverse(root.left) ;
  4.         // 中序遍历
  5.        traverse(root.right)
  6.         // 后序遍历
  7.     }

递归算法的时间复杂度怎么算？⼦问题个数乘以解决⼀个⼦问题需要的时间。
画出递归树，看他的节点数。 用节点数乘以每个计算出来每个节点要花费的时间。

动态规划

动态规划问题的⼀般形式就是求最值。动态规划其实是运筹学的⼀种最优化
⽅法，只不过在计算机问题上应⽤⽐较多，⽐如说让你求最⻓递增⼦序列
呀，最⼩编辑距离呀等等。
既然是要求最值，核⼼问题是什么呢？求解动态规划的核⼼问题是穷举。因
为要求最值，肯定要把所有可⾏的答案穷举出来，然后在其中找最值呗。
⾸先，动态规划的穷举有点特别，因为这类问题存在「重叠⼦问题」，如果
暴⼒穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优
化穷举过程，避免不必要的计算
⽽且，动态规划问题⼀定会具备「最优⼦结构」，才能通过⼦问题的最值得
到原问题的最值。
另外，虽然动态规划的核⼼思想就是穷举求最值，但是问题可以千变万化，
穷举所有可⾏解其实并不是⼀件容易的事，只有列出正确的「状态转移⽅
程」才能正确地穷举。
以上提到的重叠⼦问题、最优⼦结构、状态转移⽅程就是动态规划三要素。
具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移⽅
程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因，我
来提供我研究出来的⼀个思维框架，辅助你思考状态转移⽅程：
明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base
case。

第一题：斐波那契数列

第二题：零钱兑换（leecode 322）

  1.     /**
  2.      * 首先确定状态 、确定dp函数的定义 、明确选择 、明确base case
  3.      * 其实本质上就是遍历树，找到从根节点到最低节点最短的一条路径
  4.      * 难点：如果节点值为0，返回0。  节点值为负数，就封死这条路
  5.      * 把重点放在统计节点之间连线的个数。  即：节点负责路通不通。节点连线是计数依据
  6.      */
  7.     public static int minValue(int[] coins,int amount) {
  8.         //    因为只有金额数量不一样，所以状态是金额总量
  9.         if (amount == 0) {
  10.             return 0;
  11.         }
  12.         int temp = 0;
  13.         int result = Integer.MAX_VALUE;
  14.         for (int i = 0; i < coins.length; i++) {
  15.             if(amount-coins[i] >= 0) {
  16.                 temp = minValue(coins,amount-coins[i]);
  17.             }else {
  18.                 continue;
  19.             }
  20.             result = Math.min(result,temp+1);
  21.         }
  22.         return result==Integer.MAX_VALUE?-1:result;
  23.     }
  24. }

动态规划里的状态即是变量的意思。