动态规划汇总

作者推荐

视频算法专题

本文相关知识点

动态规划的时间复杂度优化

简介

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

优势场景

适用场景

最优化原理：假设问题的最优解所包括的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

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

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

大致步骤

一，状态定义。 二，转移方程 。 三，初始状态。 四，填表顺序。 五，返回值。

博文合集

字符串dp

回文

LeetCode困难题：

【动态规划】【字符串】132.分割回文串 II

【动态规划】【二分查找】【去重】730. 统计不同回文子序列

【动态规划】【回文】【字符串】1147. 段式回文

【动态规划】【回文】【字符串】1278分割回文串 III

【动态规划】【记忆化搜索】【回文】1312让字符串成为回文串的最少插入次数

【动态规划】【字符串】【回文】：2911得到 K 个半回文串的最少修改次数

暂无题解：1745 1771 2472 2484

k个连续区间

每个区间非空，且任何元素都属且仅属于一个区间。

动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本

【动态规划】【字符串】C++算法：140单词拆分

交叉区间

每个区间非空，一个元素可以属于1个或更多区间。

【动态规划】【记忆化搜索】【C++算法】664. 奇怪的打印机

其它

动态规划】【字符串】C++算法：正则表达式匹配

【动态规划】C++算法：最长有效括号

【动态规划】C++算法：44 通配符匹配

【动态规划】【字符串】87扰乱字符串

【动态规划】【滑动窗口】C++算法：3003 执行操作后的最大分割数量

【动态规划】【 数学】C++算法：514自由之路

【动态规划】 【字典树】C++算法：472 连接词

动态规划】【二分查找】C++算法 466 统计重复个数

动态规划】【字符串】【C++算法】940. 不同的子序列 II

【动态规划】【字符串】【状态压缩】943 最短超级串

【动态规划】【逆向思考】【C++算法】960. 删列造序 III

【动态规划】【字符串】【行程码】1531. 压缩字符串

【动态规划】【字符串】【前缀和】1639通过给定词典构造目标字符串的方案数

【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数

【数位dp】【动态规划】【KMP】1397. 找到所有好字符串

【动态规划】【字符串】1092. 最短公共超序列

【动态规划】【字符串】2167移除所有载有违禁货物车厢所需的最少时间

数论组合数学dp

【动态规划】LeetCode2552：优化了6版的1324模式

【动态规划】LeetCode2111:使数组 K 递增的最少操作次数

map|动态规划|单调栈|LeetCode975:奇偶跳

【动态规划】C++算法：115.不同的子序列

【动态规划】C++算法312 戳气球

【动态规划】C++算法：446等差数列划分 II – 子序列

【动态规划】C++算法：403.青蛙过河

【动态规划】C++ 算法458:可怜的小猪

【动态规划】【记忆化搜索】C++算法：546移除盒子

【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组

【动态规划】【C++算法】639 解码方法 II

【动态规划】【数学】【C++算法】805 数组的均值分割

【动态规划】【C++算法】801. 使序列递增的最小交换次数

【动态规划】879. 盈利计划

【动态规划】【组合数学】【C++算法】920播放列表的数量

【动态规划】【C++算法】956 最高的广告牌

【深度优先搜索】【组合数学】【动态规划】1467.两个盒子中球的颜色数相同的概率

【数学】【记忆化搜索 】【动态规划】964. 表示数字的最少运算符

【动态规划】【数学】1388. 3n 块披萨

【组合数学】【动态规划】【前缀和】1735生成乘积数组的方案数

【动态规划】【子序列除重】【C++算法】1987不同的好子序列数目

【动态规划】【子数组划分】【前缀和】1977. 划分数字的方案数

【动态规划】【C++算法】2188. 完成比赛的最少时间

【动态规划】【C++算法】2518. 好分区的数目

【动态规划】【数组】1416. 恢复数组

【动态规划】【数学】【C++算法】1449. 数位成本和为目标值的最大数字

【动态规划】【中位数】【C++算法】1478. 安排邮筒

【动态规划】【C++算法】1563 石子游戏 V

【动态规划】【记忆化搜索】【状态压缩】1681. 最小不兼容性

【动态规划】【位运算】1787. 使所有区间的异或结果为零

【动态规划】【状态压缩】【C++算法】1815 得到新鲜甜甜圈的最多组数

【动态规划】【组合数学】1866. 恰有 K 根木棍可以看到的排列数目

【状态压缩】【动态规划】【C++算法】1125.最小的必要团队

【动态规划】【前缀和】【推荐】2463. 最小移动总距离

【动态规划】【状态压缩】LCP04 覆盖

矩阵

【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II

【动态规划】【矩阵快速幂】【KMP】LeetCode2851. 字符串转换

数位dp

C++数位动态规划算法：统计整数数目 详细

【数位dp】【动态规划】C++算法：233.数字 1 的个数

【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字

图论dp、树形dp

动态规划】【广度优先】LeetCode2258:逃离火灾

【map】【动态规划】LeetCode2713:矩阵中严格递增的单元格数

【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数

【动态规划】【 矩阵】【逆向思考】C++算法174地下城游戏

【动态规划】【矩阵】C++算法329矩阵中的最长递增路径

【动态规划】【C++算法】741摘樱桃

【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径

【动态规划】【map】【C++算法】1289. 下降路径最小和 II

【归并排序】【图论】【动态规划】【 深度优先搜索】1569将子数组重新排序得到同一个二叉搜索树的方案数

【动态规划】【图论】【C++算法】1575统计所有可行路径

【动态规划】【树形dp】【C++算法】968监控二叉树

【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II

【动态规划】【图论】【C++算法】1928规定时间内到达终点的最小花费

【动态规划】【图论】【C++算法】1301. 最大得分的路径数目

【动态规划】【树形dp】【深度优先搜索】LCP 26. 导航装置

其它

【动态规划】【C++算法】1340. 跳跃游戏 V

【动态规划】【C++算法】1335 工作计划的最低难度

【动态规划】【精度】1883. 准时抵达会议现场的最小跳过休息次数

【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠

【动态规划】【前缀和】【数学】2338. 统计理想数组的数目

【动态规划】【C++算法】LeetCoce996正方形数组的数目

【动态规划】【C++算法】2742. 给墙壁刷油漆

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。