动态规划

一般是二维问题

首先，动态规划问题的一般形式就是求最值。 动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。

既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。

动态规划这么简单，就是穷举就完事了？我看到的动态规划问题都很难啊！

首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。

另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」，才能正确地穷举。

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移方程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因，我来提供我研究出来的一个思维框架，辅助你思考状态转移方程：

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

备忘录方法

备忘录方法是动态规划方法的变形。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上的

动态规划的 3 个性质（必要条件）

能采用动态规划求解的问题的一般要具有 3 个性质：

1. 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

3. 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

和分治法区别

动态规划适用于分解得到的子问题往往不是相互独立的。在这种情况下如果采用分治法，有些子问题会被重复计算多次，动态规划通过记录已解决的子问题，可以避免重复计算。

和贪心算法区别

动规是由前一个状态推导出来的，而贪心是局部直接选最优

动态规划流程

一般流程就是三步：暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法。

就思考流程来说，就分为一下几步：找到状态和选择 -> 明确 dp 数组/函数的定义 -> 寻找状态之间的关系

1. 确定状态

研究最优策略的最后一步、化为子问题

2. 转移方程

根据子问题定义直接得到

3. 初始条件和边界情况

细心，考虑周全

4. 计算顺序

利用之前的计算结果

动态规划框架

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

动态规划题目特点

1. 计数

(1) 有多少种方式走到右下角

(2) 有多少种方法选出 k 个数使得和是 Sum

2. 求最大值最小值

(1) 从左上角走到右下角路径的最大数字和

(2) 最长上升序列长度

3. 求存在性

(1) 取石子游戏， 先手是否必胜

(2) 能不能选出 k 个数使得和是 Sum

动态规划应用

1. 路径问题(最小路径和、不同路径)

2. 子序列问题(最长回文子序列、不同的子序列)