动态规划面试宝典
最后更新于
这有帮助吗？
最后更新于
这有帮助吗？
模块一：初识动态规划
模块二：动态规划的套路
模块三：举一反三，突破套路
把状态细化成了“状态”、“状态存储”，把状态转移方程中的“初始状态”提取出来重点标注了。 状态其实就是状态表示本身。 状态存储就是需要你考虑如何存储状态的解。 初始状态就是需要你考虑状态解的边界条件，做特殊处理（这个应该是需要注意的，很多人会忽略其重要性）。
一般来说穷举从来都不是一个好方法。除非你要的结果就是所有的不同组合，而不是一个最值。但即便是求所有的不同组合，在计算的过程中也仍然会出现重复计算的问题，我们将这种现象称之为重叠子问题。、
贪心算法：
根据问题来建立数学模型，一般面试题会定义一个简单模型；
把待求解问题划分成若干个子问题，对每个子问题进行求解，得到子问题的局部最优解；
把子问题的局部最优解进行合并，得到最后基于局部最优解的一个解，即原问题的答案。
所谓局部最优，就是只考虑“当前”的最大利益，既不向前多看一步，也不向后多看一步，导致每次都只用当前阶段的最优解。
虽然纯粹的贪心算法作用有限，但是这种求解局部最优的思路在方向上肯定是对的，毕竟所谓的整体最优肯定是从很多个局部最优中选择出来的，因此所有最优化问题的基础都是贪心算法。
所有贪心的思路就是我们最优化求解的根本思想，所有的方法只不过是针对贪心思路的改进和优化而已。回溯解决的是正确性问题，而动态规划则是解决时间复杂度的问题。
贪心算法本身的局限性：
不能保证求得的最后解是最佳的；
不能用来求最大或最小解问题；
只能求满足某些约束条件的可行解的范围。
递归的目的是求解
回溯+递归的目的是枚举所有组合的解，并取最优解返回
没有回溯，递归只能获得一个解或者无解，获得的解不一定是最优解
递归是一种算法结构，回溯是一种算法思想
所谓最优化问题，就是指在某些约束条件下，决定可选择的变量应该取何值，使所选定的目标函数达到最优的问题。
最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。
堆栈与递归的状态存储在计算机中，实现递归必须建立在堆栈的基础上，这是因为每次递归调用的时候我们都需要把当前函数调用中的局部变量保存在某个特定的地方，等到函数返回的时候再把这些局部变量取出来。
递归这种形式，正是赋予了回溯这种可以回退一步的能力：它通过堆栈保存了上一步的当前状态。
剪枝与优化这两种方法：
利用预设条件减少搜索路径，优化最优组合搜索方案（硬币的优化）；
利用重叠子问题，避免重叠子问题的计算。
在于向你尽可能详细地展示递归的过程，但凡遇到递归问题，你最好都能画出递归树，这对你分析算法的复杂度，寻找算法低效的原因都有巨大帮助。
消除重叠子问题，即消灭重复计算的过程。我们可以创建一个备忘录（memorization），在每次计算出某个子问题的答案后，将这个临时的中间结果记录到备忘录里，然后再返回。
数组（Array），通常对于简单的问题来说，使用一维数组就足够了。在后续的课程中，你会看到更为复杂的状态存储过程，届时我会指导你使用更高维度（二维甚至三维）的数组来存储状态。
哈希表（Hash table），如果你存储的状态不能直接通过索引找到需要的值（比如斐波那契数列问题，你就可以直接通过数组的索引确定其对应子问题的解是否存在，如果存在你就拿出来直接使用），比如你使用了更高级的数据结构而非简单的数字索引，那么你还可以考虑使用哈希表，即字典来存储中间状态，来避免重复计算的问题。
我们回想一下在上一课中提到过的问题，就有不少是不存在重叠子问题的，比如八皇后问题。既然没有重叠子问题，那么通过备忘录来对其优化加速，又从何谈起呢？
有些问题虽然看起来像包含“重叠子问题”的子问题，但是这类子问题可能具有后效性，但我们追求的是无后效性。所谓无后效性，指的是在通过 A 阶段的子问题推导 B 阶段的子问题的时候，我们不需要回过头去再根据 B 阶段的子问题重新推导 A 阶段的子问题，即子问题之间的依赖是单向性的。
备忘录解法可以归纳为：
用数组或哈希表来缓存已解的子问题答案，并使用自顶向下的递归顺序递归数据；
基于递归实现，与暴力递归的区别在于备忘录为每个求解过的子问题建立了备忘录（缓存）；
为每个子问题的初始记录存入一个特殊的值，表示该子问题尚未求解（如无此记录，或像求解斐波那契数列题目中那样初始化成 0）；
在求解过程中，从备忘录中查询。如果未找到或是特殊值，表示未求解；否则取出该子问题的答案，直接返回。
递归是分治处理问题的方法分为两部分：递和归，递是自上而下，分解问题，归是自下而上收集计算处理结果。如果要反过来就会变成先收集计算结果后分解问题在逻辑上是矛盾的。 另把递归改为迭代方式，也是在用 stack 或 queue 等模拟压栈和出栈，用在堆上分配内存的方式解决栈大小限制的问题，本质还是自上而下的。
任何穷举算法（包括递归在内）都需要一个终止条件。在动态规划中，我们将其称之为初始化状态。
我们按照上面提到的凑硬币的思路，找出子问题与原问题之间会发生变化的变量。在动态规划中，我们将其称之为状态参数。同时，你应该注意到了，这个状态在不断逼近初始化状态。而这个不断逼近的过程，叫做状态转移。
初始化状态=>确定状态参数=>涉及决策的思路
状态缓存与循环
在带备忘录的递归算法中，每次都需要查询子问题是否已经被计算过。针对这一问题，我们可以思考一下，是否有方法可以不去检查子问题的处理情况呢？在执行 A 问题的时候，确保 A 的所有子问题一定已经计算完毕了。
我们的思路是从目标问题开始，不断将大问题拆解成子问题，然后再继续不断拆解子问题，直到子问题不可拆解为止。通过备忘录就可以知道哪些子问题已经被计算过了，从而提升求解速度。
动态规划问题的核心是写出正确的状态转移方程，为了写出它，我们要先确定以下几点：
初始化状态：由于动态规划是根据已经计算好的子问题推广到更大问题上去的，因此我们需要一个“原点”作为计算的开端。在硬币找零问题中，这个初始化状态是 memo[0]=0；
状态：找出子问题与原问题之间会发生变化的变量。在硬币找零问题中，这个状态只有一个，就是剩余的目标兑换金额 k；
决策：改变状态，让状态不断逼近初始化状态的行为。在硬币找零问题中，挑一枚硬币，用来凑零钱，就会改变状态。一般来说，状态转移方程的核心参数就是状态。接着，我们需要自底向上地使用备忘录来消除重叠子问题，构造一个备忘录（在硬币找零问题中，它叫 memo。为了通用，我们以后都将其称之为 DP table）。
一般来说，状态转移方程的核心参数就是状态。
动态规划一定具备以下三个特征：
重叠子问题：在穷举的过程中（比如通过递归），存在重复计算的现象；
无后效性：子问题之间的依赖是单向性的，某阶段状态一旦确定，就不受后续决策的影响；
最优子结构：子问题之间必须相互独立，或者说后续的计算可以通过前面的状态推导出来。
优先考虑使用贪心算法的可能性； 然后是暴力递归进行穷举（但这里的数据规模不大）； 还是不行呢？选择动态规划！
数据不可排序
最小的 k 个数
数据不可交换
全排列
给定一个没有重复数字的序列，返回所有的可能的全排列
接着我们列出了辨别一个算法问题是否该使用动态规划来解的五大特点： 求最优解问题（最大值和最小值）； 求可行性（True 或 False）； 求方案总数； 数据结构不可排序（Unsortable）； 算法不可使用交换（Non-swappable）。
动态规划问题，先看如何进行穷举，再去找重叠子问题以及无后效性，以及最优子结构 通常要求的题目为最优解问题，最大值，最小值所构成的最优方案，方案总数，就是能够实现的方案数量