leetcode
凑硬币
Leetcode_experience
一、动态规划
动态规划
->
求最值
->
穷举
<-
存在重叠子问题，无法直接暴力穷举（指数级别的复杂度）
->
引入DP
Table
对于一个整体求最值问题，拆解为多个子问题，求解子问题的最优，从而得到原问题最值。
在动态规划的过程中，对于DP
Table的遍历顺序有多种情况：正向、反向、斜向（例如左下到右上）等等。使用的标准在于1：遍历过程中所使用的状态以及计算过。2：遍历的重点是所需结果的状态。
1、斐波那契
对于诸如斐波拉契数列，直接的暴力解法相当于求一遍递归树所有的节点，即2^n的复杂度。其中原因就是重复计算了大量节点。
解决方法1--自顶向下：可以在递归调用重复调参的同时，使用一个数组（备忘录）来记录已经结算过的子问题的值。这样就达到了空间换时间的目的，最终时间为n。
解决方法2--自底向上：可以将递归问题转化为迭代问题。从当前已经解决的问题出发，构建DP
Table，循环计算。
2、凑零钱
对于指定金额，给出在币值范围内进行组合的最少数量解。
解决方法1--暴力递归：遍历币值列表，计算金额-当前币值i的最
