区间DP模型
区间DP模型
给出一个序列，明确要求分割成K个连续区间，要求我们计算这些区间的某个最有性质
相关题目：
LC813 最大平均和的分组 LC1278 分割回文串 III
LC410 分割数组的最大值 LC1335. 工作计划的最低难度
第二种区间DP模型
适用情景：针对整个序列，经过操作，获取最优解。
感觉这种类型的题目普遍有些复杂，模型并不特别适用，定义好dp数组，状态的转移的确是从小区间到大区间，但具体怎么筛选，还是需要根据题目具体展开。而且感觉整体难度对于个人来说偏高
整体思路：按照区间大小，依次枚举整个区间的所有子区间的结果，最后整个区间的最优结果是从这些子区间中的最优结果逐步结算得出的（怎么突然感觉是贪心呢？？？难道贪心属于动归的特例？？？）
全站分卷索引 · 42 卷
- 1代码随想录知识星球精华（最强八股文）第五版（算法篇）
- 2找出所有子集的异或总和再求和
- 3哈希表
- 4哈希冲突
- 5红黑树与AVL树
- 6平衡二叉树（AVL树）
- 7将有序数组转换为二叉搜索树
- 83. 分割（组合问题）
- 9方法论
- 10509. 斐波那契数
- 1162. 不同路径
- 1296. 不同的二叉搜索树
- 13322. 零钱兑换
- 14爬楼梯
- 15背包小总结 (01背包、完全背包)
- 16子序列问题
- 17674. 最长连续递增序列
- 18115. 不同的子序列
- 19总结
- 20技巧总结
- 21时间序列模型
- 22区间DP模型
- 23664. 奇怪的打印机
- 24编辑距离
- 25回文串
- 26DP递推公式总结
- 27排序算法
- 28其他算法
- 294. 分别用递归和非递归方式实现二叉树先序、中序和后序遍历
- 302. TOP N问题
- 313. 分布式的TOP N问题
- 322. Astar数据结构 + 公式
- 334. 代码实现
- 345. 总体代码
- 35堆排序
- 36单源最短路
- 37思维导图
- 38链表
- 39回溯
- 40贪心
- 41动态规划
- 42排序