套路
一般用于求最值，基本上就是穷举
-
重叠子问题，用于保证时间效率高
-
最优子结构，子问题的最优解组合成原问题的最优解，用于保证正确性。
经典问题
凑零钱问题
leetcode 322
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
-
首先确定状态，也就是原问题和子问题中变化的量，本题中就是目标金额
-
然后确定dp函数的定义，当目标金额为
n的时候，至少需要dp(n)个硬币 -
然后确定选择并择优，也就是对于每个状态，可以做出什么选择来改变当前的状态，本题中就是选择一种硬币，然后目标就会减少（状态发生变化）
-
最后明确base case，即递归终止的条件，本题中就是
dp(0)=0，dp(n<0)=-1
dp(n) = dp(n-coin) + 1;
dp(n): for each coin: 1 + dp(n-coin)
