状压dp 状压矩阵行号：3276. 选择矩阵中单元格的最大得分 状压走过位置的集合：3283. 吃掉所有兵需要的最多移动次数

区间dp 从数组的左右两端不断缩短，求解关于某段下标区间的最优值。 一般定义：f[i][j] 表示下标区间 [i, j] 的最优值。 最长回文子序列 516. 最长回文子序列 其它 5. 最长回文子串：记搜和递推两种写法 3040. 相同分数的最大操作数目 II(1709)：有点意思 3277. 查询子数组最大异或值：区间dp嵌套区间dp

3277. 查询子数组最大异或值 给你一个由 n 个整数组成的数组 nums，以及一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri]。 对于每一个查询，你需要找出 nums[li..ri] 中任意 子数组 的 最大异或值。 数组的异或值 需要对数组 a 反复执行以下操作，直到只剩一个元素，剩下的那个元素就是 异或值： 对于除最后一个下标以外的所有下标 i，同时将 a[i] 替换为 a[i] XOR a[i + 1] 。 移除数组的最后一个元素。 返回一个大小为 q 的数组 answer，其中 answer[i] 表示查询 i 的答案。 示例 1： 输入： nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]] 输出： [12,60,60] 解释： 在第一个查询中，nums[0..2] 的子数组分别是 [2], [8], [4], [2, 8], [8, 4], 和 [2, 8, 4]，它们的异或值分别为 2, 8, 4, 10, 12, 和 6。查询的答案是 12，所有异或值中的最大值 ...

山峰序列 给定一个数组nums = [i, ..., j]，如果这个数组先递增再递减，那么称这个数组为山峰序列 现在给你一个数组，需要重排这个数组，请问有多少种方法可以使重排后的数组为山峰序列 答案可能过大，所以你需要输出答案对于 998244353 的余数 示例 1： 123输入：n = 2, nums = [1,2,3]输出：4解释：[1,2,3],[1,3,2],[2,3,1],[3,2,1] 示例 2： 123输入：n = 3, nums = [3,3,3]输出：1解释：[3,3,3] 示例 3： 123输入：n = 3, nums = [1,2,1]输出：3解释：[1,1,2],[1,2,1],[2,1,1] 提示： 1 <= n <= 10^5 1 <= nums[i] <= 10^9 这个问题相当于去除所有最大数值的元素后，对于剩下的元素组成的数组，查找可以组成的数组的数量，即组合数 例如示例1，去除3后，1和2可以组成4种情况：[],[1],[2],[1,2] 可以发现，如果元素不重复，那么答案很简单，就是2^n 但是如果元素有重复那么直接查 ...

3276. 选择矩阵中单元格的最大得分 给你一个由正整数构成的二维矩阵 grid。 你需要从矩阵中选择 一个或多个 单元格，选中的单元格应满足以下条件： 所选单元格中的任意两个单元格都不会处于矩阵的 同一行。 所选单元格的值 互不相同。 你的得分为所选单元格值的总和。 返回你能获得的 最大 得分。 示例 1： 输入： grid = [[1,2,3],[4,3,2],[1,1,1]] 输出： 8 解释： 选择上图中用彩色标记的单元格，对应的值分别为 1、3 和 4 。 示例 2： 输入： grid = [[8,7,6],[8,3,2]] 输出： 15 解释： 选择上图中用彩色标记的单元格，对应的值分别为 7 和 8 。 提示： 1 <= grid.length, grid[i].length <= 10 1 <= grid[i][j] <= 100 动态规划：枚举值域，状压行号 12345678910111213141516171819202122232425262728class Solution { public int maxSc ...

状态机dp 一般定义 f[i][j] 表示在 nums[:i] 在状态 j 下的最优值。一般 j 都很小 代表题目是「买卖股票」系列 121. 买卖股票的最佳时机 122. 买卖股票的最佳时机 II 123. 买卖股票的最佳时机 III 188. 买卖股票的最佳时机 IV 309. 买卖股票的最佳时机含冷冻期 714. 买卖股票的最佳时机含手续费

线性dp 经典线性dp 对于字符串s和t，一般定义f[i][j]表示对s[0:i]和t[0:j]的状态 最长公共子序列(LCS) 1143. 最长公共子序列 最长递增子序列(LIS) 300. 最长递增子序列 一维dp 发生在前缀/后缀之间的转移，例如从 f[i−1] 转移到 f[i]，或者从 f[j] 转移到 f[i] 一维线性dp 2140. 解决智力问题(1709) 2944. 购买水果需要的最少金币数(1709) 2901. 最长相邻不相等子序列 II(1899): 还要输出具体方案 2896. 执行操作使两个字符串相等(2172): 需要先条件转换 特殊子序列dp 比较特殊的一类题型，递推比记忆化搜索好写 计算合法子序列的最长长度、个数、元素和等。 一般定义 f[x] 表示以元素(数字) x 结尾的合法子序列的 xxx 值（比如个数、元素和），从子序列的倒数第二个数转移过来。 2501. 数组中最长的方波(1480) 3202. 找出有效子序列的最大长度 II(1974) 3351. 好子序列的元素之和：一种比较不错的思路，可以通过这题理解特殊 ...

更多 待分类整理 需要小技巧的动态规划 石子游戏 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. 树中距离之和 2581. 统计可能的树根数目(2228) 其它树形dp 2920. 收集所有金币可获得的最大积分(2351)