树形dp 树形动态规划（Tree DP）就是在树形结构上进行的动态规划。 在树形结构中，每个节点通常连接着若干子节点，但只有一个父节点。树形DP利用了树的这种结构特点，在动态规划的过程中以节点为单位进行递推，从叶子节点开始，向上逐层计算直至根节点。 由于树形结构天然地包含了递归特性，因此递归式的DP是一种常用的方法。 换根dp 也叫二次扫描法 通常是先计算以0节点为root出发的结果，记为res[0]，而以其它节点为root出发的结果可以通过与res[0]的差值相加得到 834. 树中距离之和 2581. 统计可能的树根数目(2228) 其它树形dp 2920. 收集所有金币可获得的最大积分(2351)

数位dp 数位分解：将一个数按照各个数位进行分解，例如将123分解为1、2、3。数位dp主要涉及到对这些数位的状态进行动态规划，通常，状态表示当前处理到的位置、当前已经得到的数值等信息。 可用于解决如数位上包含特定数字、数字之和等问题。 2376. 统计特殊整数(2120) 2719. 统计整数数目(2355) 3260. 找出最大的 N 位 K 回文数(2370)

划分型dp 对数组或者字符串进行位置划分，划分成几个子数组或者子字符串 判定能否划分 一般定义f[i]表示长为i的前缀a[:i]能否划分，枚举最后一个子数组的左端点L，从f[L]转移到f[i]，并考虑a[L:j]是否满足要求 2369. 检查数组是否存在有效划分(1780) 计算划分最优值 定义f[i]表示对于前缀[0:i)所得到的最优解，枚举最后一个子数组的左端点L，从f[L]转移到f[i]，并考虑子数组[L:i)对最优解的影响 2707. 字符串中的额外字符(1736) 约束划分个数 定义f[i][j]表示对于前缀[0:i)划分成j个连续子数组所得到的最优解，枚举最后一个子数组的左端点L，从f[L][j-1]转移到f[i][j]，并考虑子数组[L:i)对最优解的影响 2911. 得到 K 个半回文串的最少修改次数(2608) 不相交区间 2008. 出租车的最大盈利(1872)

数据结构优化dp 其它优化dp 3181. 执行操作可获得的最大总奖励 II

网格图dp 在网格图上的移动 62. 不同路径 1594. 矩阵的最大非负积

背包 0-1背包 给定一个背包的容量c和n个物品，第i个物品的体积为w[i]，价值为v[i]。每个物品选或不选，求体积和不超过capacity时的最大价值和 核心思路：枚举第i个物品选或不选 初始化一个二维数组dp，其中dp[i][j]表示在考虑前i个物品、背包容量为j的情况下的最大总价值 dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) 背包至多装capacity 求方案数 求最大价值和（传统01背包） 背包恰好装capacity 求方案数: 494. 目标和 求最大价值和 求最小价值和 背包最少装capacity 求方案数 求最小价值和 其它 3180. 执行操作可获得的最大总奖励 I 完全背包 给定一个背包的容量c和n种物品，第i种物品的体积为w[i]，价值为v[i]。每种物品无限次重复选，求体积和不超过capacity时的最大价值和 考虑第i个物品选不选时，可以重复选择，所以这里考虑dp[i][c]时，可能多次更新dp[i][c-w[i]] + v[i] dp[i][c] = max(dp[i-1] ...

dp深似海 “系统过去的历史只能通过现阶段的状态去影响系统的未来”——研究生算法课程老师对动态规划的描述，感觉挺不错的 分类参考了灵神的dp题单 记忆化搜索和递推是dp的两种实现方式 网格图dp 背包dp 线性dp 状态机dp 划分型dp 区间dp 状压dp 数位dp 树形dp dp回溯 其它待分类dp 注意事项 如果动态转移方程不是按顺序的，那么需要注意不能直接赋值f[i+1][j] = f[i][j];，因为这样可能会覆盖之前动态转移的结果（注释的是按顺序的动态转移写法） 相关题解：3276. 选择矩阵中单元格的最大得分 1234567f[i+1][j] = Math.max(f[i+1][j], f[i][j]);// f[i+1][j] = f[i][j]; // 这里是错的，不能赋值for (int s = map.get(nums.get(i)), t = 0; s > 0; s -= t) { t = s & -s; if ((j & t) > 0) continue; f[i+1][j|t] = ...