其他来源：数据结构/算法学习笔记

动态规划问题（Dynamic Programming）

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

动态规划的特点：

1. 存在「重叠子问题」
2. 具备「最优子结构」
   要符合「最优子结构」，子问题间必须互相独立。
3. 列出正确的「状态转移方程」(实际上就是描述问题结构的数学形式： f(n)=xxxx)
   思考状态转移方程：
   确定 base case -> 确定「状态」-> 确定「选择」 -> 定义 dp 数组/函数的含义

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移方程是最困难的。

动态规划框架：

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

参考：
labuladong 的算法小抄