树形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) 约束划分个数 定义f[i][j]表示对于前缀[0:i)划分成j个连续子数组所得到的最优解，枚举最后一个子数组的左端点L，从f[L][j-1]转移到f[i][j]，并考虑子数组[L:i)对最优解的影响 2911. 得到 K 个半回文串的最少修改次数(2608) 不相交区间 2008. 出租车的最大盈利(1872)

数据结构优化dp 前缀和优化dp 3381. 长度可被 K 整除的子数组的最大元素和: 前缀和优化dp 3251. 单调数组对的数目 II(2323): 前缀和优化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++) { // 前后双指针+哈希表记录 ...

Stream Stream::max(int 和 Integer的不同) 12345int intArr[] = new int[]{1, 2, 3};Arrays.stream(intArr).max().getAsInt(); Integer integerArr[] = new Integer[]{1, 2, 3};Arrays.stream(integerArr).max(Integer::compareTo).get(); Stream中 int 和 Integer 互相转换 mapToObj: int -> Integer 三种方式：mapToObj(Integer::valueOf), mapToObj(i->Integer.valueOf(i)), mapToObj(i->i) 123// int数组转换成Integer列表int nums = new int[]{1, 2, 3};List<Integer> list = Arrays.stream(nums).mapT ...

《Redis设计与实现》：笔记 指令 Redis指令参考：Redis Order 结构 对象9 type：对象的类型 REDIS_STRING，字符串对象 REDIS_LIST，列表对象 REDIS_HASH，哈希对象 REDIS_SET，集合对象 REDIS_ZSET，有序集合对象 数据类型 汇总一个类型对应的多种编码 REDIS_STRING，字符串对象 REDIS_ENCODING_INT 要求字符串对象保存的是整数值， 并且这个整数值可以用 long 类型来表示 ptr属性里面（将 void* 转换成 long ）， 并将字符串对象的编码设置为 int 通过 APPEND 命令， 向一个保存整数值的字符串对象追加了一个字符串值，对象的编码就会从int变成raw REDIS_ENCODING_RAW 字符串对象保存的是一个字符串值，且长度大于 39 字节 ptr指针指向一个SDS对象（sdshdr） REDIS_ENCODING_EMBSTR 字符串对象保存的是一个字符串值，且长度小于等于 39 字节 和raw一样，ptr指针指向一个SDS对象，但它的 ...

Markdown 段内换行 在一行的结尾插入两个或以上的空格 链接地址 链接和文字分开，例如google,baidu 1234[google],[baidu][google]:https://www.google.com[baidu]:https://www.baidu.com 网址链接 用<>包围，例如1234@qq.com（GFM拓展语法可以自动识别，不需要用<>） 1<1234@qq.com> 表情符号 :smile:: :smile: :laughing:: :laughing: 表格 左对齐 居中对齐 右对齐 01 hello a 02 world b 1234| 左对齐 | 居中对齐 | 右对齐 || :--- | :--: | ---: || 01 | hello | a || 02 | world | b | 任务列表 [x] 已完成 [ ] 未完成 12- [x] 已完成- [ ] 未完成 锚点 Markdown 段内换行 链接地址 网址链接 表情符号 表格 任务列表 锚点 拓展 MySql ...