概述

动态规划是通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，常常适用于有重叠子问题和最优子结构性质的问题。

简单来说，动态规划其实就是，给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。

找零问题

钞票面额为1,5,11时：
f(n)=min{f(n−1),f(n−5),f(n−11)}+1

青蛙跳台阶

斐波那契即可：
f(n) = f(n-1) + f(n-2)

动态规划的解题思路

动态规划的特点

动态规划从较小问题的解，由交叠性质，逐步决策出较大问题的解，所以称为自底向上的解法。

动态规划有几个典型特征，最优子结构、状态转移方程、边界、重复子问题、无后效性。在青蛙跳阶问题中：
•f(n-1)和f(n-2) 称为 f(n) 的最优子结构
•f(n)= f(n-1) + f(n-2)就称为状态转移方程
•f(1) = 1, f(2) = 2 就是边界
•比如f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重复子问题

最优子结构：最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。
无后效性：无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。
重复子问题：不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

解题步骤

定义数组元素的含义：例如定义dp[i]的含义
找出数组元素之间的关系式：也就是dp数组各个元素之间的递推关系，即状态转移方程
确定初始条件：一般为dp[0]、dp[1]等初始值的初始化

例题（见PPT）：不同路径、最小路径和、编辑距离。
其中“编辑距离”见如下提示：

对“dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。”的补充理解：

以 word1 为 "horse"，word2 为 "ros"，且 dp[5][3] 为例，即要将 word1的前 5 个字符转换为 word2的前 3 个字符，也就是将 horse 转换为 ros，因此有：

(1) dp[i-1][j-1]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 2 个字符 ro，然后将第五个字符 word1[4]（因为下标基数以 0 开始） 由 e 替换为 s（即替换为 word2 的第三个字符，word2[2]）

(2) dp[i][j-1]，即先将 word1 的前 5 个字符 horse 转换为 word2 的前 2 个字符 ro，然后在末尾补充一个 s，即插入操作

(3) dp[i-1][j]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 3 个字符 ros，然后删除 word1 的第 5 个字符

尝试空间优化：dp[i]、dp[i][j]的求解往往是根据前一个、前（上）一行元素转移而来，转移过后的值后续有可能不再使用，此时就可以将一维优化为常数空间，二维优化为一维。

不同算法策略的选择

一个问题是该用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间状态的转移方式决定的！

每个阶段只有一个状态->递推；
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。

主定理

主理论（Master Theorem）是用来解决递归关系式的一种方法，特别是用于分析某些类型的递归算法的时间复杂度。

假设某个递归算法的时间复杂度递归公式为： $T(n) = a \times T ( \frac{n}{b} ) + n^d, 其中a\gt1, b\gt1, d\gt0$
这个表达式其实是在表达：将规模为n的问题转换为 $a$ 个规模为 $\frac{n}{b}$ 的子问题，在合并这些子问题的解时需要花费 $O(n^d)$ 时间。