近年来，国内外科技公司的算法面试中，动态规划几乎成了必考题型。
动规题目类型众多，又没有固定的解题模板，初学者往往摸不着头脑，有时还会混淆动规和递归，所以动态规划又被称为“新人杀手”。
不过动态规划的难，更多是因为初学者不知道怎么入门。学会正确的思考模式和解题流程，掌握动态规划其实并不难。
九章侯卫东老师针对所有动态规划题型，总结了一套4步解题法。
作为清华学霸，全国算法竞赛金牌，ACM全球总决赛选手，FLAG资深面试官，侯卫东老师凭借丰富的刷题和面试经验，用“3枚硬币”深入浅出地讲解动态规划，具体怎么样？通过下面的视频来感受下吧。
视频中的题目如下：
你有三种硬币，分别面值2元，5元和7元，每种硬币都有足够多。买一本书需要27元。如何用最少的硬币组合正好付清，不需要对方找钱？
关键词“用最少的硬币组合”——求最值问题，可以用动态规划来解决。
状态在动态规划中的作用属于定海神针。解动态规划时需要开一个数组，这里的“状态”就是指数组的每个元素f[i]或f[i][j]代表什么。
这道题中，我们不知道最优策略是什么，但最优策略肯定是K枚硬币a1,a2……aK面值加起来是27。
现在问题变成了：最少用多少枚硬币可以拼出27-aK。也就是将原问题（27）转化成了一个子问题，而且规模更小（27-aK）。
这种与原问题内核一致，但是规模更小的问题，就叫子问题。
为了简化定义，我们设状态f(X)=最少用多少枚硬币拼出X。所以问题就从求f(X)变成求f(X-aK)
我们目前还不知道最后的硬币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}
对于任意X，f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}
实际面试中，如果正确列出转移方程，问题基本就解决一半了。
很多同学基本也可以做到写出状态转移方程，但真正写程序的时候往往会出现很多错误或问题。
这就涉及到在代码前的两个重要步骤，就是我们4步解题法的第三步和第四步。
f[X] = min{f[X-2]+1, f[X-5]+1, f[X-7]+1}的边界情况是X-2, X-5或者X-7不能小于0（硬币面值为正）
f[1] =min{f[-1]+1, f[-4]+1,f[-6]+1}=正无穷,表示拼不出1
特殊情况：本题的F[0]对应的情况为F[-2]、F[-5]、F[-7]，按照上文的边界情况设定结果是正无穷。
但是实际上F[0]的结果是存在的（即使用0个硬币的情况下），F[0]=0。
这种用转移方程无法计算，但是又实际存在的情况，就必须通过手动定义。
而从0之后的数值是没矛盾的，比如F[1]= F[1-2]+1= F[-1]+1=正无穷（正无穷加任何数结果还是正无穷）；F[2]= F[2-2]+1= F[0]+1=1……
那么开始计算时，是从F[1]、F[2]开始？还是从F[27]、F[26]开始呢？
当我们要计算F[X]（等式左边，如F[10]）的时候，等式右边（f[X-2], f[X-5], f[X-7]等）都是已经得到结果的状态，这个计算顺序就是OK的。
实际就是从小到大的计算方式
（偶有例外的情况我们后边再讲）。
例如我们算到F[12]的时候，发现F[11]、F[10]、F[9]都已经算过了，这种算法就是对的；
而开始算F[27]的时候，发现F[26]还没有算，这样的顺序就是错的。
回到这道题，采用动态规划的算法，每一步只尝试三种硬币，一共进行了27步。算法时间复杂度（即需要进行的步数）为27*3。
按照以上4步套路，基本上可以解决绝大多数类型的动态规划题。
除了最值型动态规划，想要了解4步法在更多类型动态规划中的运用，可以来听侯卫东老师的《
动态规划专题班
》。
长按扫码，点击免费试听即可
或点击下方“阅读原文”
