前言

??「 动态规划 」作为算法中一块比较野的内容，没有比较系统的分类，只能通过不断总结归纳，对各种类型进行归类。「 动态规划 」（即 Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学 以及 生物信息学中使用的，通过把原问题分解为相对简单的「 子问题 」的方式求解「 复杂问题 」的方法。
??「 动态规划 」是一种算法思想：若要解一个给定问题，我们需要解其不同部分（即「 子问题 」），再根据「 子问题 」的解以得出原问题的解。要理解动态规划，就要理解 「 最优子结构 」 和 「 重复子问题 」。
??本文将针对以下一些常用的动态规划问题，进行由浅入深的系统性讲解。首先来看一个简单的分类，也是今天本文要讲的内容。

直接跳到末尾 参与投票，获取粉丝专属福利。

文章目录

• 前言
• 一、递推问题
• • 1、一维递推
  • 2、二维递推
• 二、线性DP
• • 1、最小花费
  • 2、最大子段和
  • 3、最长单调子序列
• 三、二维DP
• • 1、最长公共子序列
  • 2、最小编辑距离
  • 3、双串匹配问题
• 四、记忆化搜索
• 五、背包问题
• • 1、0/1 背包
  • 2、完全背包
  • 3、多重背包
  • 4、分组背包
  • 5、依赖背包
• 六、树形DP
• 七、矩阵二分
• 八、区间DP
• 九、数位DP
• 十、状态压缩DP
• 十一、斜率DP
• 十二、连通性DP
• 粉丝专属福利