动态规划题目特点：
计数
1.有多少种方式走到右下角
2.有多少种方法选出k个数使得和是sum
求最大最小值
1.从左上角走到右下角路径的最大字数和
2.最长上升子序列长度
** 求存在性**
1.取石子游戏，先手是否必胜
2,能不能选出K个数字使得和是sum
coin change
有三种硬币，分别面值为2元，5元，7元，每种硬币都有足够多;
买一本书需要27元;
如何用最少的硬币组合正好付清，不需要对方找钱
tag：求最大最小值dp
动态规划组成部分一：确定状态
最后一步
-
虽然现在不知道最优策略是什么，但是最优策略肯定是K枚硬币a1，a2，ak...面值加起来是27
-
所以一定有一枚最后的硬币：ak
-
除掉这枚硬币，前面硬币的面值加起来是27-ak
上图关键点：
-
我们不关心前面K-1枚硬币是怎么拼出27 - ak的（可能有一种拼法，也可能有100种拼法），而且我们现在甚至不知道ak和K，但是我们确定前面的硬币拼出了27-ak
-
因为是最优策略，所以27-ak的硬币数一定要最少，否则就不是最优策略了。
子问题
-
所以我们就要求：最少用多少枚硬币可以拼出27-ak
-
原问题是最少用多少枚硬币拼出27
-
我们将原问题转化成了一个子问题，而且规模更小：27-ak
-
为了简化定义，我们设状态f(X) = 最少用多少枚硬币拼出X
最后那枚硬币ak只可能是2，5或者7
-
如果ak是2，f(27) = f(27-2) +1 （加上最后这枚硬币2）
-
如果ak是5，f(27) = f(27-5)+1（加上最后这枚硬币5）
-
如果ak是7，f(27) = f(27-7) +1 （加上最后这枚硬币7）
-
除此之外，再无其他可能
-
因为需要求最少的硬币数，所以
-
f(27) = min{f(27-2)+1,f(27-5)+1,f(27-7)+1}
动态规划组成部分二：转移方程
-
设状态f[X] = 最少用多少枚硬币拼出X
-
对于任意X，f[27]= min{f[27-2]+1,f[27-5]+1,f[27-7]+1}
动态规划组成部分三：初始条件和边界情况
两个问题：
-
X-2,X-5或者X-7小于0怎么办
-
什么时候停下来
如果不能拼出Y，就定义f[Y] = 正无穷
-
如f[-1] = f[-1] = ... = 正无穷
所以f[1] = min{f[-1]+1,f[-4]+1,f[-6]+1} = 正无穷，表示拼不出1
初始条件：f[0] = 0
动态规划组成部分四：计算顺序
-
拼出X所需要的最少硬币数：f[X]= min{f[X-2]+1,f[X-5]+1,f[X-7]+1}
-
初始条件：f[0] = 0
-
然后计算f[1]、f[2]、...f[27]
-
当我们计算到f[X]时，f[X-2],f[X-5],f[X-7]都已经得到结果了
