线性DP
线性动态规划简介
线性动态规划：具有「线性」阶段划分的动态规划方法统称为线性动态规划（简称为「线性 DP」）
如果状态包含多个维度，但是每个维度上都是线性划分的阶段，也属于线性 DP。比如背包问题、区间 DP、数位 DP 等都属于线性 DP
线性 DP 问题的划分方法有多种方式：
- 按照「状态的维度数」进行分类
- 一维线性 DP 问题
- 二维线性 DP 问题
- 多维线性 DP 问题
- 按照「问题的输入格式」进行分类
- 单串线性 DP 问题
- 双串线性 DP 问题
- 矩阵线性 DP 问题
- 无串线性 DP 问题
单串线性 DP 问题
单串线性 DP 问题中最经典的问题就是「最长递增子序列（Longest Increasing Subsequence，简称 LIS）」
双串线性 DP 问题
双串线性 DP 问题中最经典的问题就是「最长公共子序列（Longest Common Subsequence，简称 LCS）」