《王道程序员求职宝典》笔记 - 第10章 动态规划与贪心算法

分治法

分治法就是把一个大问题分割成许多简单的小问题之后解决这些小问题，然后利用小问题的结果求得大问题的结果的思想。

分治法的问题的特征

• 问题规模缩小之后变得更容易解决。
• 问题可以分解为若干个规模较小的问题。
• 利用分解开的小问题的解可以求得大问题的解。
• 各个子问题之间是相互独立的，彼此不包含公共的子问题。

动态规划

动态规划问题是指一个问题首先能变成递归求解的问题，之后能够通过从底向上的方式求出我们期望的值。

一般步骤

1.将题进行模型化，之后找到递归关系，通常是想办法通过作假设分开两种情况去掉一个变量数目，得到F[i]与F[i-1]之间的关系。

例如LCS问题中，通过假设最后一个字母是否相同得到两种情况，然后根据两种情况分别写出i, j, i-1和j-1在目标函数中的关系。

2.找到最底层的边界值

例如LCS问题中，只要i=0或j=0函数的结果都是0。

3.根据底层边界值和得到的递归关系，如何求得顶层数据的结果

LCS问题中的那个表格。

之后用程序实现就可以了，这里应该是可以先填表格再探索状态转移方程。

适用的问题

动态规划适用的问题是多阶段决策问题，例如LCS问题就是在两个字符串中连续选择不同位置的字符。

字符串编辑距离问题中，多次采用不同操作也属于多阶段决策。

字符串编辑问题用的思想既有穷举也有递归，递归写出来之后再利用备忘录法进行优化的，主要是没事很容易通过条件分开来找到递归公式，所以不适用上节的一般条件。

贪心算法

贪心算法就是在每一步都选择局部最优解，然后得到结果的过程。

习题

做不明白。