# 动态规划
# 1. 概念
动态规划（Dynamic Programming），是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划是一种方法论，而不是一种具体的算法。
动态规划通过将问题进行拆分成可解决的子问题，从而解决问题。
子问题类型：
- 子问题之间如果是并行的，则需要采取分治
- 子问题之间如果有依赖，则需要采取动态规划
动态规划要素：
- 确定状态定义和初始状态
- 确定状态转移条件
- 确定状态转移方程
- 分析复杂度和优化空间
# 子问题重复
记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。因为记忆化搜索确保了每个状态只访问一次，它也是一种常见的动态规划实现方式。
# 2. 类型
- 区间dp
- 数位dp
- 树形dp
# 3. 解决问题
# 1. 路径问题
- 数字三角形
# 2. 字符串
- 最长公共子序列
- 最长递增子序列