算法知识图谱总览 / 组目录 / 组索引

动态规划基础族

动态规划basicintermediate15 节点
组目录:排序与基础算法族栈队列与单调结构族堆与优先队列族并查集族区间查询与分块族线段树族可持久化数据结构族平衡二叉搜索树族高级树结构族哈希与链表族动态规划基础族DP优化族高级DP族搜索算法族图基础与遍历最短路族生成树族连通性族网络流族二分图与匹配族树算法族欧拉与哈密顿族图论高级专题字符串匹配族字典树与AC自动机族后缀结构族后缀自动机族回文族Lyndon与周期族数论基础族数论进阶族数论高级族组合计数基础族组合进阶族多项式与FFT族生成函数族线性代数族概率族数值方法族大整数与数制族凸包族平面扫描与几何求交计算几何基础与度量树链剖分与动态树可持久化数据结构分块与根号算法莫队算法族高级线段树与离线专题(topic 域)调度与其他专题IO与常数优化族位运算族Python竞赛特性族调试与对拍族随机化与元启发式族博弈论族离线与杂项技巧族竞赛策略族工具链族前沿趋势组
← 上一组G-A-10 全局返回总览 下一组 →G-A-12

组简介

本组 15 个知识点，属于 动态规划 域，覆盖阶段 basic / intermediate。

优先级分布：P0 ×7 · P1 ×8

阶段分布：basic ×5 · intermediate ×10

节点目录 (15 个)

节点 ID名称阶段优先级简介例题数
dp-basic动态规划基础basicP0最优子结构/无后效性/子问题重叠，状态定义与转移方程3
dp-memo记忆化搜索basicP0自顶向下DFS+缓存，DP的递归实现方式2
dp-knapsack010-1背包basicP0每个物品取/不取，O(nW)转移，滚动数组优化空间3
dp-knapsack-complete完全背包basicP0每件物品无限取，正序遍历容量3
dp-knapsack-multiple多重背包intermediateP1每件物品有限数量，二进制拆分或单调队列优化2
dp-knapsack-group分组背包intermediateP1物品分组，每组最多选一件2
dp-linear线性DP(LIS/LCS)basicP0一维序列上的DP，最长递增子序列/最长公共子序列3
dp-interval区间DPintermediateP0f(i,j)表示区间[i,j]最优，枚举合并点k，O(n^3)3
dp-tree树形DPintermediateP0树上递归DP，DFS后序传递子树最优解到父节点3
dp-tree-knapsack树上背包intermediateP1树形DP+背包结合，依赖关系物品选择2
dp-state状压DPintermediateP1集合状态编码为二进制整数，适合小规模状态空间3
dp-count计数DPintermediateP1利用DP记忆化求计数问题，划分子集不重不漏2
dp-number数位DPintermediateP1按数位逐位枚举，记忆化记录合法状态，大区间计数3
dp-dagDAG上的DPintermediateP1有向无环图上的最长/最短路，拓扑序转移3
dp-probability概率/期望DPintermediateP1概率顺推/期望逆推，可能需高斯消元处理环依赖3

学习路径提示

本组内存在 9 条前置依赖边（prerequisite），推荐先掌握前置知识点，再进入依赖它的节点。

推荐阅读顺序（拓扑序）
动态规划基础 → 记忆化搜索 → 0-1背包 → 完全背包 → 多重背包 → 分组背包 → 线性DP(LIS/LCS) → 区间DP → 树形DP → 树上背包 → 状压DP → 计数DP → 数位DP → DAG上的DP → 概率/期望DP
所属领域
动态规划 · 域内共 3 组
同域下一组
G-A-12 · DP优化族