更多 待分类整理 需要小技巧的动态规划 石子游戏 V（2087 几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。 游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。 只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。 返回 Alice 能够获得的最大分数 。 示例 1： 12345输入：stoneValue = [6,2,3,4,5,5]输出：18解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。最后一轮 Alice 只能将行分成 [ ...

动态规划回溯 通过回溯找到动态规划过程中的具体路径 具体来说，就是从最终答案开始，根据动态规划转移方程的条件，一步一步往回找 01背包+回溯: 689. 三个无重叠子数组的最大和 完全背包+回溯: 1449. 数位成本和为目标值的最大数字 一维线性dp+回溯: 2901. 最长相邻不相等子序列 II(1899)

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

数位dp 数位分解：将一个数按照各个数位进行分解，例如将123分解为1、2、3。数位dp主要涉及到对这些数位的状态进行动态规划，通常，状态表示当前处理到的位置、当前已经得到的数值等信息。 可用于解决如数位上包含特定数字、数字之和等问题。 数位dp模板 2376. 统计特殊整数(2120) 123456789101112131415161718192021222324class Solution { public int countSpecialNumbers(int n) { char cs[] = String.valueOf(n).toCharArray(); int memo[][] = new int[cs.length][1 << 10]; for (int i = 0; i < cs.length; i++) Arrays.fill(memo[i], -1); return dfs(0, 0, true, false, cs, memo); } // ...

划分型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) 3538. 合并得到最小旅行时间：三维dp：区间[i,j]+剩余合并次数leftK（记忆化搜索写法） 约束划分个数 定义f[i][j]表示对于前缀[0:i)划分成j个连续子数组所得到的最优解，枚举最后一个子数组的左端点L，从f[L][j-1]转移到f[i][j]，并考虑子数组[L:i)对最优解的影响 2911. 得到 K 个半回文串的最少修改次数(2608) 3599. 划分数组得到最小 XOR：经典二维+枚举左端点，记忆化和递推两种写法 不相交区间 2008. 出租车的最大盈利(1872)

数据结构优化dp 前缀和优化dp 3381. 长度可被 K 整除的子数组的最大元素和: 前缀和优化dp 3251. 单调数组对的数目 II(2323): 前缀和优化dp 单调栈优化dp 3578. 统计极差最大为 K 的分割方式数: 区间最大值最小值 + 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] ...

哈希大法 枚举右维护左 对于双变量问题，例如两数之和 (a_i + a_j = t)，可以枚举右边的 (a_j)，转换成单变量问题。也就是在 (a_j) 左边查找是否有 (a_i = t - a_j)，这可以用哈希表维护。 用哈希记录之前的数，并用于判断情况是否成立 1. 两数之和：经典的枚举右维护左 421. 数组中两个数的最大异或值: 对于每一位bit，枚举右维护左 3381. 长度可被 K 整除的子数组的最大元素和: 枚举右维护之前每个余k索引的前缀和最小值 [3404. 统计特殊子序列的数目]：题目式子变形 + 枚举右维护左 二重哈希 第一个哈希的value被当作key放入第二个哈希 3092. 最高频率的 ID 字符串哈希 请看字符串哈希 前缀和+哈希表 请看前缀和 遍历过程维护集合大小 在遍历的过程中，我们可以通过前后双指针（滑动窗口），动态维护一个哈希表，来确保当前窗口的元素集合大小不超过某个值k，如下代码所示 12345678910111213for (int i = 0, j = 0; i < n; i++) { // 前后双指针+哈希表记录 ...

最近公共祖先 描述 问题就是寻找树上两个节点的最近公共祖先节点 边权重均等查询 此题难度超过2500 现有一棵由 n 个节点组成的无向树，节点按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi, wi] 表示树中存在一条位于节点 ui 和节点 vi 之间、权重为 wi 的边。 另给你一个长度为 m 的二维整数数组 queries ，其中 queries[i] = [ai, bi] 。对于每条查询，请你找出使从 ai 到 bi 路径上每条边的权重相等所需的 最小操作次数 。在一次操作中，你可以选择树上的任意一条边，并将其权重更改为任意值。 注意： 查询之间 相互独立 的，这意味着每条新的查询时，树都会回到 初始状态 。 从 ai 到 bi的路径是一个由 不同 节点组成的序列，从节点 ai 开始，到节点 bi 结束，且序列中相邻的两个节点在树中共享一条边。 返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 条查询的答案。 示例 1： 1234567输 ...