动态规划

这里简要讲一下，遇到动态规划问题应该如何快速找到出发点

我们以例子来说明：

# 题目：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，再给一个总金额 n，

#问你最少需要几枚硬币凑出这个金额，如果不可能凑出，则回答 -1 。

#比如说，k = 3，面值分别为 1，2，5，总金额 n = 11，那么最少需要 3 枚硬币，即 11 = 5 + 5 + 1 。下面走流程。

首先，我们要先找到 f(n)，这是最终问题, 在这里，即是金额为n时，f(n)代表最少需要的硬币数

接着，要找到 f(n)与子项的关系！ 固现在开始就是要将f(n)进行分解，一般是思维，是想到与 f(n-1)的关系！ 然而这里并不是，因为f(n-1)代表的是当金额为n-1时，需要的最少硬币数。  真实的联系是，最后一枚币时，前面已经到达了最小值。

# f(n) = 1 +Min{f(n-ci)|i->[0,k] }  (n>0) 

然而动态规划还有一个点，叫自下而上！ 也就是说，我要先算 f(n),就得先算出 f(1),f(2).....

对应该题，我们应该要先算出 当金额为1时，最少多少个币，金额为2时，最小多少个币...最后才有金额为n时，金额多少币！

固多数情况下，我们都需要用一个map来存这些历史数据，key就是金额，value就是次数！ 只有这里存储过后，才能很方便的使用上面发现的公式： f(n) = 1 +Min{f(n-ci)|i->[0,k] }  (n>0)

好了，最后总结动态规划的下手俩点：

1、找到子项联系，可能是 f(n)与f(n-1) 的关系，也可能是 f(n) = 1+极值  的关系

2、找到自下而上的关系！ 即是要求出 f(1),f(2)...最终求得f(n)

3、第2条与第1条联用一般就是俩个FOR循环