动态规划

动态规划题目的特点

• 计数
• 求最大最小值
• 求存在性

最后都是得出一个最优值，而不是所有的可能性。

动态规划解题思路

有2，5，7三种类型的硬币，求用这三种硬币拼出来的总量为27，但是用的硬币个数最小。

组成部分一：确定状态

也就是说，在解动态规划问题的时候需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么

确定状态需要两个意识：

最后一步

也就是最后存在的解

例如：

这个题一定存在一个解，即K枚硬币组合在一起达到了总量为27

关键点1

我们不关心前面的k-1枚硬币是怎么拼出来27-aK的（可能有一种拼法，可能有100种拼法），而且我们现在甚至还不知道ak和K，但是我们确定前面的硬币拼出了27-ak

    ##### 关键点2

因为是最优策略，所以拼出27-ak的硬币数量一定要最小，否则这就不是最优策略了

需要最小的硬币数，所以：

这个时候，我们可以用递归方法解题

但是有一个问题，递归是从上到下进行计算的，这样的话会产生大量的重复运算

所以说，这不是一个好的解法，解决方法就是将计算结果保存下来，改变计算顺序

看到这里是不是感觉好像记忆化递归的逆序，没错！这就是动态规划！

总结：首先思路是递归方法，但是这里面有着大量的重复计算，然后我们进阶为了记忆化递归，但是记忆化递归太过于占据内存，所以有了动态规划。

组成部分二：转移方程

设状态F[X] =最少用多少枚硬币拼出X

对于任意X，

组成部分三：初始条件和边界条件

两个问题：X-2，X-5，X-7小于0怎么办？什么时候停下来？

所以定义初始条件：

那么什么时候定义初始条件，那就是用转移方程计算不出来的，这个时候就需要定义初始条件

在本题中：令F[0] = 0

组成部分四：计算顺序

• 初始条件：f[0] = 0;
• 然后计算f[1]，f[2]，……，f[27]
• 当我们计算到f[x]时候，f[x-2]，f[x-5]，f[x-7]都已经得出结果了

与递归相比：动态规划优化了太多的时间复杂度，递归往往是指数级别的，而动态规化往往是乘积级别