清华大学全国算法竞赛金牌，ACM国际大学生程序设计竞赛全球总决赛选手。FLAG资深面试官。

动态规划题目类型多，难度高，没有固定模板，死记硬背没用。作为大厂高频面试题，动态规划问题的识别与解决一直是难点所在，往往也是决定面试成功与否的最终关卡。不过不用怕，我总结了解决动态规划类问题的4步套路，分享给大家。先备一份见面礼——7.2个G的5月最新大厂求职资料，感兴趣的同学可以长按识别白嫖~望笑纳

• FLAG高频动态规划66题
• 国内外大厂最新算法面试题
• 一线互联网公司真题解析

礼包部分内容，长按扫码即可领取

4步套路，解决动态规划问题

2、转移方程，把问题方程化
3、按照实际逻辑设置初始条件和边界情况
4、确定计算顺序并求解

你有三种硬币，分别面值2元，5元和7元，每种硬币都有足够多。买一本书需要27元。如何用最少的硬币组合正好付清，不需要对方找钱？

关键词“用最小的硬币组合正好付清”——“最小的组合”，求最值问题，动态规划。

优先使用大面值硬币——7+7+7+5=26 额？可求解目标是27啊……
实际正确答案：7+5+5+5+5=27，才用了5枚硬币。
所以这里贪心算法是不正确的。

第一步，确定问题状态。

动态规划问题求解需要先开一个数组，并确定数组的每个元素f[i]代表什么，就是确定这个问题的状态。类似于解数学题中，设定X，Y，Z代表什么。

A、确定状态首先提取【最后一步】

最优策略必定是K枚硬币a1, a2,…, aK 面值加起来是27。

找出不影响最优策略的最后一个独立角色，这道问题中，那枚最后的硬币“aK”就是最后一步。把aK提取出来，硬币aK之前的所有硬币面值加总是27- aK
因为总体求最硬币数量最小策略，所以拼出27- aK 的硬币数也一定最少（重要设定）。

B、转化子问题。最后一步aK提出来之后，我们只要求出“最少用多少枚硬币可以拼出27- aK”就可以了。

这种与原问题内核一致，但是规模变小的问题，叫做子问题。

为简化定义，我们设状态f(X)=最少用多少枚硬币拼出总面值X。
我们目前还不知道最后的硬币aK面额多少，但它的面额一定只可能是2/5/7之一。
除此以外，没有其他的可能了。

至此，通过找到原问题最后一步，并将其转化为子问题。
为求面值总额27的最小的硬币组合数的状态就形成了，用以下函数表示：

第二步，转移方程，把问题方程化。

实际面试中求解动态规划类问题，正确列出转移方程正确基本上就解决一半了。

但是请问：这与递归有什么不同？？

// f(X)返回最少用多少枚硬币拼出X
// 0元钱只要0枚硬币
// 初始化用无穷大（为什么是正无穷？）
// 最后一枚硬币是2元
// 最后一枚硬币是5元
// 最后一枚硬币是7元
 

要算f(27)，就要递归f(25)、f(22)、f(20)，然后下边依次递归……（三角形表示）。

问题明显——重复递归太多。

这是求f(27)，还可以勉强递归。如果求f(100)呢？简直是天文数字。最终结果就是递归超时。

求总体最值，一定优先考虑动态规划


需要掌握的动态规划面试解题技巧还包括坐标型、位操型、序列型、博弈型、背包型、双序列以及一些高难面试题解。

本文篇幅有限无法逐一讲清，大家来白嫖我的在线分享吧（纯干货）。

第三步，按照实际逻辑设置边界情况和初始条件。

【必做】否则即使转移方程正确也大概率无法跑通代码。

故对边界情况设定如下：

特殊情况：本题的F[0]对应的情况为F[-2]、F[-5]、F[-7]，按照上文的边界情况设定结果是正无穷。

但是实际上F[0]的结果是存在的（即使用0个硬币的情况下），F[0]=0。


这种用转移方程无法计算，但是又实际存在的情况，就必须通过手动定义。

这里手动强制定义初始条件为：F[0]=0.

第四步，确定计算顺序并计算求解

那么开始计算时，是从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]还没有算，这样的顺序就是错的。

很显然这样的情况下写一个FOR循环就够了。

回到这道题，采用动态规划的算法，每一步只尝试三种硬币，一共进行了27步。算法时间复杂度（即需要进行的步数）为27*3。

与递归相比，没有任何重复计算。

1、这是求最值问题，用动态规划方式求解。2、进入求解过程，先确定问题状态

• （最优策略中使用的最后一枚硬币aK）
  -子问题转化 （最少的硬币拼出更小的面值27-aK）
  （求min是因为题目要求求最小）
  4、设置初始条件和边界情况 f[0] = 0, 如果不能拼出Y，f[Y]=正无穷
  5、确定计算顺序并计算求解
  

实际上按照以上4步套路，基本上可以应对绝对大多数的动态规划面试题。

1.设X和Y都是n位二进制整数，若按普通乘法规则计算，要进行O(n2)步运

算才能得到XY的乘积，若用分治法来计算，可有效地降低其复杂性。简述采用分治法求解XY乘积的基本过程。

解：即为大整数的乘法（参照书上2.4节P29）：

2.扩展Hanoi塔问题：设a,b,c,d是4个塔座。开始时，在塔座a上有一叠共n

个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n，现要求采用递归算法将塔座a上的这一叠圆盘移到塔座d上，并仍按同样顺序叠置。

在移动圆盘时应遵守以下移动规则：

规则1：每次只能移动1个圆盘；

规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；

规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c,d中任一塔座上。

设计算法实现一种移动方案，并分析算法的时间复杂度。

3.比较分治法、动态规划法和贪心算法的使用条件。

解：分治法和递归是紧密相联系的，分治法就是把大问题分解成小问题，然后大问题的解可以通过小问题的解得出来。小问题是相互独立的，可以递归解决。分治法所能解决的问题一般具有以下几个特征：

（1）该问题的规模缩小到一定的程度就可以容易地解决；

（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；

（3）利用该问题分解出的子问题的解可以合并为该问题的解；

（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。如下问题使用分治法解决：计算逆序，找出平面上最近的点，等等

经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。例如典型的Fibonacci数列的求解。两种动态规划算法：备忘录和迭代

贪心法是自然的方法，也是最直观的方法，贪心法的当前选择依赖于已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择，但是该方法不能保证最后得出的解是最优的，需要反复选

动态规划（Dynamic Programming，简称DP），虽然抽象后进行求解的思路并不复杂，但具体的形式千差万别，找出问题的子结构以及通过子结构重新构造最优解的过程很难统一，并不像回溯法具有解决绝大多数问题的银弹（)。为了解决动态规划问题，只能靠多练习、多思考了。本文主要是对一些常见的动态规划题目的收集，希望能有所帮助。难度评级受个人主观影响较大，仅供参考。

动态规划求解的一般思路： 

　　判断问题的子结构（也可看作状态），当具有最优子结构时，动态规划可能适用。

　　求解重叠子问题。一个递归算法不断地调用同一问题，递归可以转化为查表从而利用子问题的解。分治法则不同，每次递归都产生新的问题。

　　重新构造一个最优解。

　　动态规划的一种变形，使用自顶向下的策略，更像递归算法。

　　初始化时表中填入一个特殊值表示待填入，当递归算法第一次遇到一个子问题时，计算并填表；以后每次遇到时只需返回以前填入的值。

　　实例可以参照矩阵链乘法部分。 

　　假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。 

/* 该方法用于搜索某一行的横向放置瓷砖的状态数,并把这些状态累加上row-1 行的出发状态的方法数 * @name state 由上一行决定的这一行必须放置竖向瓷砖的地方，s的二进制表示中的1 就是这些地方 /** 该列和下一列放置一块横向的瓷砖 */ /** 对较小的数进行状压，已提高效率 */ /* 如果i-1行的出发状态某处未放，必然要在i行放一个竖的方块， * 所以我对上一行状态按位取反之后的状态就是放置了竖方块的状态