Skip to content

Latest commit

 

History

History
219 lines (153 loc) · 60.2 KB

AlgorithmList.md

File metadata and controls

219 lines (153 loc) · 60.2 KB

Powered by: NEFU AB-IN

[TOC]

GPT Prefix

请你将按以下规则总结该题的题意以及思路

  1. 题意和思路都写成一个自然段的形式，题意一个，思路一个，并用 Markdown 形式发给我。如果想分行，请用 <br />隔开
  2. Markdown中的数学公式，latex公式，都用'$'包裹起来，而不是\
  3. 如果思路只有代码，根据我的代码和注释，写文字的思路
  4. 最后加上代码的复杂度

贪心

题目名称 题目链接 难度 标签 备注
成为 K 特殊字符串需要删除的最少字符数 https://leetcode.cn/problems/minimum-deletions-to-make-string-k-special/description 中等 贪心、哈希表、逆向思维 题意：给定一个字符串 $word$ 和一个整数 $k$，需要通过删除字符，使字符串满足以下条件：对于字符串中任意两个字符 $i$ 和 $j$，它们在字符串中的出现频率之差 $
找出有效子序列的最大长度 I https://leetcode.cn/problems/find-the-maximum-length-of-valid-subsequence-i/description/ 中等 贪心、记忆化搜索 题意：给定一个整数数组 $nums$，需要找出其最长的有效子序列的长度。一个子序列是通过从原数组中删除若干元素（或不删除任何元素）且保持剩余元素顺序的数组。如果子序列 $sub$ 的长度为 $x$，且满足 $(sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x-2] + sub[x-1]) % 2$，则称其为有效子序列
思路：
贪心：最长的有效子序列可能为以下三种情况之一：全为奇数、全为偶数或奇偶交替。使用 odd := sum(x & 1 for x in nums) 快速统计数组中奇数的数量。通过 sum((x & 1) ^ (y & 1) for x, y in pairwise(nums)) 计算数组中相邻元素奇偶性差异对数，从而得出奇偶交替的最长子序列长度。
**DFS + 记忆化搜索：**使用 DFS 配合记忆化搜索解决问题，通过四种初始状态分别进行递归搜索，保证覆盖所有可能的有效子序列情况。初始状态分别为：从索引 $0$ 开始，当前元素奇偶性为偶数且期望下一个元素奇偶性变化为奇数（dfs(0, 0, 1)）、当前元素奇偶性为偶数且期望下一个元素奇偶性变化为偶数（dfs(0, 0, 0)）、当前元素奇偶性为奇数且期望下一个元素奇偶性变化为偶数（dfs(0, 1, 0)）、当前元素奇偶性为奇数且期望下一个元素奇偶性变化为奇数（dfs(0, 1, 1)）。

哈希表

题目名称 题目链接 难度 标签 备注
最多能完成排序的块 II https://leetcode.cn/problems/minimum-deletions-to-make-string-k-special/description/ 中等 哈希表、单调栈 将数组 $arr$ 分成若干块，并分别排序后连接，要求最终结果与 $arr$ 的升序排序结果一致，返回最多的分块数。
哈希表：通过同时遍历 $arr$ 和排序后的数组 $sortedArr$，用哈希表记录两者元素频次的差。当哈希表中所有值均为 $0$ 时，表示可以划分出一个新的块，统计这样的分块数即可。
单调栈：栈中每个元素代表一个块的最大值。如果当前数字比栈顶小，说明需要与前面的块合并。如果当前数字比栈顶大或相等，说明可以形成一个新块。遍历完成后，栈的大小就是最多的分块数。

滑动窗口

题目名称 题目链接 难度 标签 备注
统计重新排列后包含另一个字符串的子字符串数目 II https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-ii/ 中等 滑动窗口 题意: 给定两个字符串 $word1$ 和 $word2$，如果字符串 $x$ 是 $word1$ 的一个子字符串，并且 $word2$ 是 $x$ 重新排列后的前缀，则称 $x$ 为合法子字符串。求 $word1$ 中合法子字符串的数量。
思路: 使用滑动窗口和计数的方法解决。首先通过 defaultdict （重点：Counter可以用，但是比defaultdict 慢很多）统计 $word2$ 中各字符的频次（目标计数）。然后用滑动窗口统计 $word1$ 的子字符串中字符的频次（当前计数）。滑动窗口通过双指针实现，初始窗口为空（$i = 0, j = 0$）。固定左指针，去动右指针。右指针 $j$ 向右扩展窗口，当窗口内字符频次满足 $word2$ 的频次要求时，记录当前窗口的合法子字符串数量（为 $n - j + 1$，其中 $n$ 是 $word1$ 的长度）。随后左指针 $i$ 向右移动，缩小窗口并更新字符频次。通过辅助函数 judge 判断当前窗口是否满足合法条件，整体时间复杂度为 $O(n \cdot m)$，其中 $m$ 是 $word2$ 的字符集大小。

位运算

题目名称 题目链接 难度 标签 备注
统计重新排列后包含另一个字符串的子字符串数目 II https://leetcode.cn/problems/count-substrings-that-can-be-rearranged-to-contain-a-string-ii/ 中等 滑动窗口 题意: 给定两个字符串 $word1$ 和 $word2$，如果字符串 $x$ 是 $word1$ 的一个子字符串，并且 $word2$ 是 $x$ 重新排列后的前缀，则称 $x$ 为合法子字符串。求 $word1$ 中合法子字符串的数量。
思路: 使用滑动窗口和计数的方法解决。首先通过 defaultdict （重点：Counter可以用，但是比defaultdict 慢很多）统计 $word2$ 中各字符的频次（目标计数）。然后用滑动窗口统计 $word1$ 的子字符串中字符的频次（当前计数）。滑动窗口通过双指针实现，初始窗口为空（$i = 0, j = 0$）。固定左指针，去动右指针。右指针 $j$ 向右扩展窗口，当窗口内字符频次满足 $word2$ 的频次要求时，记录当前窗口的合法子字符串数量（为 $n - j + 1$，其中 $n$ 是 $word1$ 的长度）。随后左指针 $i$ 向右移动，缩小窗口并更新字符频次。通过辅助函数 judge 判断当前窗口是否满足合法条件，整体时间复杂度为 $O(n \cdot m)$，其中 $m$ 是 $word2$ 的字符集大小。
或值至少为 K 的最短子数组 II https://leetcode.cn/problems/shortest-subarray-with-or-at-least-k-ii/description/ 中等 滑动窗口、子数组 OR/AND/GCD 通用模板、ST、位运算 **题意：**给定一个非负整数数组 $nums$ 和一个整数 $k$，需要找到 $nums$ 中最短的非空子数组，使得该子数组所有元素的按位或运算结果至少为 $k$。如果不存在这样的子数组，返回 $-1$。
思路：
1. ST + 二分 / 滑动窗口：通过二分或者滑动窗口，找到临界的为k的子数组，因为越长肯定或值越不小。所以固定一个端点，去单调数列中，找到临界的另一个端点即可

ST2. 子数组运算（如 OR、AND、GCD)的求解问题：（可不掌握）

d = dict() key 是右端点为 i 的子数组 OR, value 是该子数组左端点的最大值,记住模版的这句话
每次遍历数组时，对于当前元素 $x$，将字典中的所有 OR 值与 $x$ 按位或生成新的 OR 值，并更新到字典中，同时添加仅包含 $x$ 的子数组作为新的 OR 值。这样可以高效记录所有可能的 OR 组合。当字典中存在 OR 值 $\geq k$ 时，立即计算该子数组的长度并更新最小值。这种方法充分利用了 OR 运算的单调性，通过维护有效状态避免了重复计算，OR
3. 子数组运算（如 OR、AND、GCD)的求解问题：Log Trick：

下面有说思路，这里只放代码image-20250118194913892
找到按位或最接近 K 的子数组 https://leetcode.cn/problems/find-subarray-with-bitwise-or-closest-to-k/ 中等 子数组 OR/AND/GCD 通用模板、位运算 题意：给定一个整数数组 nums 和一个目标值 k，需要找到数组 nums 中一个连续子数组，使其所有元素的按位或运算结果与 k 的绝对差最小。子数组必须是数组中连续的非空元素子集，返回最小的绝对差值。
思路：
为了求解最优子数组的按位或结果接近 k 的问题，可以从暴力解法优化到高效方法。暴力方法需要枚举所有可能的子数组，时间复杂度为 $O(n^2)$。（这个思路就是j从i-1开始，往回开始遍历，将新的数，加入到i-1往前的集合中）
通过按位或的单调递增性质，我们动态更新从某个起点出发的按位或结果，而无需重复计算整个子数组的按位或，从而避免了暴力解法的重复计算。同时，结合按位或的特性：如果当前按位或结果已经包含目标值 $k$ 的所有位（即 $OR \
数组最后一个元素的最小值 https://leetcode.cn/problems/minimum-array-end/description/ 中等 位运算 题意：给定两个整数 $n$ 和 $x$，需要构造一个长度为 $n$ 的正整数数组 $nums$，满足以下条件：
1. 对于所有 $0 \leq i &lt; n - 1$，$nums[i+1] > nums[i]$（严格递增）。
2. 数组 $nums$ 中所有元素的按位与（AND）结果为 $x$。 返回数组中最后一个元素 $nums[n-1]$ 的最小可能值。
**思路：**为了满足按位与结果为 $x$，$x$ 的二进制中每一位为 1 的位置，所有数组元素在对应位上必须为 1；而 $x$ 中为 0 的位置可以自由填充 0 或 1。最小化 $nums[n-1]$ 的方法是：从低位到高位依次检查 $x$ 的每一位，如果某位为 0，则将 $n-1$ 的二进制位逐一填入这些 0 位中，填充完成后右移 $n$ 的值。填充顺序按递增规则（如 $000, 001, 010$）确保数组满足严格递增条件，同时保证 $nums[n-1]$ 最小。最终结果为将 $x$ 的固定部分与填充部分合并后所得的数。
比如 x = "0b10010"， n = 3; 那么第一个数为 10010，第二个为10011，第三个为10110，所以第三个也就是把 10 填进了 x 的 0 的二进制位中
按位与结果大于零的最长组合 https://leetcode.cn/problems/largest-combination-with-bitwise-and-greater-than-zero/ 中等 位运算、与运算 题意：从 candidates 中选一个子序列，要求子序列所有元素的 AND 大于 0。返回这个子序列的最长长度。
思路：说明一定存在某个二进制位，所有数字在这个二进制位上都是 1。因此，我们可以枚举每个二进制位，统计所有数字在这个二进制位上的 1 的个数，最后取最大值即可。

动态规划

题目名称 题目链接 难度 标签 备注
Beautiful Array https://codeforces.com/contest/1155/problem/D 中等 最大子段和模型 题意：给出一个长度为n的数列和数字x，经过最多一次操作将数列中的一个子段都乘x，使该数列的子段和最大。思路：分三段，设$dp[i][j]$为以$i$结尾的第$j+1$段的最大子段和
整数划分 https://www.acwing.com/problem/content/902/ 简单 计数类DP、完全背包 题意：给定一个正整数 n，请你求出 n 共有多少种不同的划分（表示成若干个正整数之和）方法。
1. 完全背包：背包容量为$n$, 第i个物品的体积为i(i = 1 ~ n)，每个物品有无限个，问恰好装满背包的方案数。
2. 计数dp：定义 $dp[i][j]$：表示使用 1∼i 的正整数分割整数 j 的方案数。不选 i：$dp[i][j]=dp[i−1][j]$， 选 i：$dp[i][j]+=dp[i][j−i]$。汇总为：$dp[n][n]$。总转移： $dp[i][j]=dp[i−1][j]+dp[i][j−i]$。优化后：$dp[j]+=dp[j−i]$
吃水果 https://www.acwing.com/problem/content/4499/ 中等 计数类DP 题目要求计算将$m$种水果分发给$n$个小朋友，使得恰好有$k$个小朋友拿到的水果与左边相邻小朋友不同的分发方案数。解法采用动态规划，定义$dp[i][j]$为前$i$个小朋友中恰有$j$个与左边水果不同的分发方案数。递推公式为$dp[i][j] = dp[i-1][j] + dp[i-1][j-1] \cdot (m-1)$，其中第一项表示第$i$个小朋友与左边相同，第二项表示第$i$个小朋友与左边不同。边界条件为$dp[1][0] = m$，表示第一个小朋友有$m$种选择且不存在不同的情况。最终答案为$dp[n][k]$，时间复杂度为$O(n \cdot k)$。
最大的和 https://www.acwing.com/problem/content/1053/ 中等 最大子段和、前后缀分解 最大子段和问题分为两种类型：连续最大子段和和非连续最大子段和。
连续最大子段和要求子段必须连续，其递推公式为：$dp[i] = \max(dp[i-1] + A[i], A[i])$，表示以第 $i$ 个元素结尾的最大连续子段和；初始条件为 $dp[0] = A[0]$。
非连续最大子段和允许子段不连续，其递推公式为：$dp[i] = \max(dp[i-1], dp[i-1] + A[i], A[i])$，表示前 $i$ 个元素中非连续子段的最大和；初始条件为 $dp[0] = \max(A[0], 0)$。连续子段和更适合保留顺序的场景，而非连续子段和适用于子段无顺序限制的问题。
最终答案分别为 $\max(dp[i])$ 和 $dp[n-1]$。
最大上升子序列和 https://www.acwing.com/problem/content/3665/ 困难 LIS模型、树状数组 给定一个长度为$n$的整数序列$a = [a_1, a_2, \ldots, a_n]$，要求选出一个严格上升的子序列，使其元素和最大。
暴力解法：定义$dp[i]$为以$a[i]$结尾的严格上升子序列的最大和，枚举每个元素$a[i]$之前的所有元素$a[j]$，若$a[j] < a[i]$，则更新$dp[i] = \max(dp[i], dp[j] + a[i])$，最终结果为$\max(dp[i])$，时间复杂度为$O(n^2)$。
优化解法：使用树状数组，首先对$a$进行离散化，将值映射到排名，树状数组维护每个排名对应的最大子序列和；对于每个元素$a[i]$，查询树状数组中所有比$a[i]$小的排名的最大值，并用$a[i]$更新树状数组，时间复杂度优化至$O(n \log n)$。最终答案为树状数组中的最大值。
最长公共上升子序列 https://www.acwing.com/problem/content/description/274/ 困难 LIS模型、LCS模型、LCIS 该题要求找到两个数组 $A$ 和 $B$ 的最长公共上升子序列（LCIS）的长度。公共上升子序列是指同时在 $A$ 和 $B$ 中出现，且元素严格递增的子序列。初始思路是使用动态规划，定义 $f[i][j]$ 表示以 $A[i]$ 和 $B[j]$ 为结尾的最长公共上升子序列的长度。当 $A[i] \neq B[j]$ 时，直接继承 $f[i-1][j]$；当 $A[i] == B[j]$ 时，通过枚举 $B$ 中的前缀位置 $k \in [1, j-1]$，找到所有满足 $B[k] &lt; B[j]$ 的 $f[i-1][k]$ 的最大值并加 $1$ 更新 $f[i][j]$。这种枚举 $k$ 的方法使时间复杂度为 $O(n^3)$。然后我们发现，b[i] > b[k] 中的 b[i] 可以替换为 a[i]，也就是求比a[i]小的b[k]的值有什么，这个地方就会被重复计算，因为a[i]是固定的，b中比a[i]小的值也是固定的。优化方法是引入一个变量 $maxv$，在每次枚举 $j$ 时提前记录 $B[1] \sim B[j-1]$ 中的最大 $f[i-1][k]$ 值，从而将复杂度降为 $O(n^2)$。这种优化利用了严格递增的特点，避免了重复计算。
最小数组和 https://leetcode.cn/problems/minimum-array-sum/description/ 困难 DP，记忆化搜索、分类讨论 时间复杂度为 $O(n \cdot op_1 \cdot op_2)$，其中 $n$ 为数组 nums 的长度。由于每个状态只会计算一次，动态规划的时间复杂度等于状态个数乘以单个状态的计算时间。本题状态个数为 $O(n \cdot op_1 \cdot op_2)$，单个状态的计算时间为 $O(1)$，因此总时间复杂度为 $O(n \cdot op_1 \cdot op_2)$。
题意：给定一个整数数组 nums 和三个整数 $k$、$op_1$、$op_2$，你可以对数组的每个数执行以下两种操作，每个数每个操作最多一次。
解法：对于每个元素，可以选择不操作、执行操作 1（将当前数减半并向上取整）、执行操作 2（若当前数大于等于 $k$ 则减去 $k$），或者同时执行操作 1 和操作 2 组合。依次递归剩余的数组，同时递减对应的操作次数 (op1 和 op2)。
目标和 https://leetcode.cn/problems/target-sum/ 中等 经典DP、01背包衍生题 题意: 给定一个非负整数数组 $nums$ 和一个整数 $target$，需要为数组中的每个元素添加 '+' 或 '-'，构造一个表达式使得其运算结果等于 $target$。返回所有满足条件的不同表达式的数量。例如，对于 $nums = [2, 1]$ 和 $target = 1$，可以构造表达式 "+2-1" 或 "-2+1"，因此答案为 $2$。
思路: 这个问题可以抽象为0-1背包问题（简化问题：找到所有子集，使得这些子集的和等于 (sum(nums) - target) / 2 或者 (sum(nums) + target) / 2，也就是背包容量，可以数学推出）。通过 DFS 结合记忆化搜索求解。我们需要将数组 $nums$ 中的每个元素赋予一个 '+' 或 '-' 符号，使得表达式的总和等于目标值 $target$。将问题转换为背包问题后，目标是寻找所有组合，使得差值满足条件。使用 DFS 枚举每个数是否选择正号或负号，并通过记忆化优化重复计算。在 DFS 中，每个状态由索引 $i$ 和当前差值 $c$ 决定：当 $i &lt; 0$ 且 $c = 0$ 时，表示成功找到一种方案。状态转移公式为从上一个状态 $dfs(i-1, c)$（当前数不选）和 $dfs(i-1, c-nums[i])$（当前数选）中累加结果。如果当前体积不足，则直接跳过选择。通过递归转移，最终返回所有合法组合的数量。时间复杂度为 $O(n \cdot t)$，其中 $t$ 为目标和的范围。
机器人可以获得的最大金币数 https://leetcode.cn/problems/maximum-amount-of-money-robot-can-earn/ 中等 DP，图论 题意：题目给定一个大小为 $m \times n$ 的网格，每个格子包含一个整数 $coins[i][j]$，可以是正数、负数或零。机器人从左上角 $(0, 0)$ 出发，到右下角 $(m-1, n-1)$。每次只能向右或向下移动，机器人需要最大化所收集的金币数量，如果 $coins[i][j] \geq 0$，则机器人获得对应数量的金币；如果 $coins[i][j] &lt; 0$，机器人会失去这些金币的绝对值；机器人有两次特殊能力，可以免除负金币的影响。需要返回机器人从起点到终点路径上可以获得的最大金币数。
思路：遇到这种图的题，从左上角到右下角，想到DP，而不是开状态数组标记路径。使用动态规划（DFS + 记忆化搜索）解决问题，定义状态为 $dfs(x, y, k)$，表示机器人在位置 $(x, y)$，还剩 $k$ 次特殊能力时的最大金币数。状态转移过程包括：
如果当前位置为负数且 $k &gt; 0$，可以选择使用特殊能力绕过负金币。
向右或向下递归搜索，并累加当前位置的金币值。
终点状态单独处理，如果有剩余特殊能力，需选择是否使用以最大化金币。
执行操作可获得的最大总奖励 II https://leetcode.cn/problems/maximum-total-reward-using-operations-ii/description/ 困难 01 背包变种、位运算优化布尔型DP（子集和问题） **题意：**给定一个整数数组 rewardValues，表示奖励的值，初始总奖励 $x$ 为 0，所有下标均未标记。每次可以选择一个未标记的下标 $i$，如果 $rewardValues[i]$ 大于当前 $x$，则可以将其加到 $x$ 并标记该下标。目标是通过最优操作顺序，使最终的总奖励最大，并返回该值。
思路：先将 rewardValues 按从小到大的顺序排序，确保尽可能选择更多的奖励值。
使用动态规划解决，定义 $f[i][j]$ 表示从前 $i$ 个奖励中是否能通过某种选择组合使总奖励为 $j$（类似01背包），转移方程为：
1. 不选第 $i$ 个奖励，状态不变：$f[i][j] = f[i-1][j]$。
2. 选第 $i$ 个奖励，前提是当前 $j \geq v$ 且 $j - v &lt; v$：$f[i][j] = f[i-1][j-v]$。
初始状态 $f[0][0] = \text{true}$。

$f[i][j]=f[i−1][j] \ or \ f[i−1][j−v]$
通过遍历可能的总奖励值，取满足条件的最大 $j$ 即为结果。通过 bitset 优化可以提升效率。
1. 优化为滚动数组：dp[j] = dp[j] or dp[j - v]
2. 位运算优化：可以不用掌握（因为只有v, 2v这个区间的在变，所以我们需要让这个区间的数 或 上一个状态的 0, v。首先创建掩码，将 f 的低v位通过与运算取出来，左移v位，最后或即可）

状态压缩

遇到有限的参数（小于20个）表示状态， 想到：状态压缩

题目名称 题目链接 难度 标签 备注
闪烁 https://www.acwing.com/problem/content/1962/ 中等 状态压缩、位运算、找环 发现规律并找环
每个元音包含偶数次的最长子字符串 https://leetcode.cn/problems/find-the-longest-substring-containing-vowels-in-even-counts/ 困难 前缀和、状态压缩、哈希表、异或（奇偶校验问题） 非常好的题！题意：给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。
思路：利用异或操作，将元音字母的奇偶性转换为二进制状态，奇变偶、偶变奇（就是将当前状态异或1即可），从而更新当前状态；通过状态压缩，将五个元音的奇偶性表示为一个二进制数（如 $01010$ 表示 'e' 和 'o' 出现奇数次），并转换为十进制存储以便处理；利用前缀和性质，当两个位置的状态相同时，其间的子字符串符合条件；哈希表则用来记录某状态首次出现的位置，快速计算最长子字符串的长度。
dict(zip("aeiou", map(int, "01234"))) 可以快速生成键值对
特别的排列 https://leetcode.cn/problems/special-permutations/description/ 困难 状态压缩、排列型 ② 相邻相关 题意: 给定一个下标从 $0$ 开始的整数数组 $nums$，其包含 $n$ 个互不相同的正整数，要求找出所有满足特别排列条件的排列数量。一个排列是特别的，当且仅当对于任意下标 $0 \leq i &lt; n - 1$，满足 $nums[i] % nums[i+1] = 0$ 或 $nums[i+1] % nums[i] = 0$。
解法: 采用状态压缩、DFS与记忆化搜索相结合的方式。由于数组长度较小（最多 $14$），可以将排列问题抽象为递归过程，并用一个 $mask$（二进制串）表示状态，其中 $1$ 表示对应数字已被选过，$0$ 表示未选过。初始状态为 $mask = 0$ 和 $prev_index = -1$，递归过程中
1. 枚举当前 $mask$ 中未选的数（$nums[i]$），并检查是否与上一个选的数（由 $prev_index$ 确定）满足特别排列条件。
2. 若条件成立，则转移到下一状态 $dp(mask
优美的排列 https://leetcode.cn/problems/beautiful-arrangement/description/ 中等 状态压缩、排列型 ① 相邻无关 题意: 给定一个整数 $n$，用从 $1$ 到 $n$ 的整数构造一个数组 $perm$（下标从 $1$ 开始），若满足以下条件之一，则该数组为优美排列：1. $perm[i]$ 能被 $i$ 整除；2. $i$ 能被 $perm[i]$ 整除。返回可以构造的优美排列的数量。
思路: 使用状态压缩和深度优先搜索（DFS）结合记忆化搜索来高效解决问题。用一个整数 $mask$ 表示当前状态，$mask$ 的第 $i$ 位为 $1$ 表示整数 $i$ 已被选入排列，否则为 $0$。递归函数 $dfs(mask, i)$ 表示已选状态为 $mask$，当前处理排列的第 $i$ 个位置，返回从此状态开始可以构造的优美排列数量。当 $mask$ 全部为 $1$ 时，表示所有整数均已选入排列，此时返回 $1$。枚举所有未被选过的数 $perm$，检查其是否满足优美排列条件（$perm % i = 0$ 或 $i % perm = 0$），若满足条件，则递归调用 $dfs(mask

差分

题目名称 题目链接 难度 标签 备注
增减序列 https://www.acwing.com/problem/content/description/102/ 简单 差分 经典题目
目标：给定一个数组，通过区间加减操作使所有元素相等，求最少操作数，以及最终可能的数组结果有多少种情况。最少操作数（因要正负数进行配对）：$min(p, q) + abs(p - q) = max(p, q)$，其中 $p$ 为数组中正数之和，$q$ 为数组中负数之和。 最终可能的结果种类数（差分数组第一项的取值范围决定）：$abs(p - q) + 1$。
岛 https://www.acwing.com/problem/content/description/2016/ 中等 差分 题意: 给定一个描述农田高度的一维数组 $a = [a_1, a_2, \dots, a_n]$，模拟暴风雨期间水位逐渐上涨的过程。每当水位上涨时，某些高度低于水位的区域会被淹没，形成被水隔开的“岛屿”。求在水位上涨的过程中，田地中能看到的最大岛屿数量
**思路：**设一块长方形的高度为a[i],假设水从a[i-1]涨到(下降到)a[i],意味着所有高度在a[i]—a[i-1]的长方形都会被淹没(露出来)，相当于这些长方形的高度差被抹平(产生)(对答案的贡献都减1(+1)).同时给一个区间减去(加上)一个数，用差分
粉刷栅栏 https://www.acwing.com/problem/content/1989/ 中等 差分，离散化，扫描线、区间重叠问题、 只需排序事件点：扫描线不需要直接操作区间，而是通过事件点的排序和处理来高效解决问题。动态维护状态：无需在每个点重新计算覆盖情况，而是通过状态的增减实现。
救生员 https://www.acwing.com/problem/content/description/1752/ 中等 扫描线、差分、区间合并、离散化 问题：枚举删除每个区间，看剩下区间组成的长度最大值。扫描线板子问题，即区间最大覆盖问题，用线段树进行优化。核心在push_up

前缀和

Python用这个 list(accumulate(nums, initial=0)) 可求一维前缀和

题目名称 题目链接 难度 标签 备注
公平摄影 https://www.acwing.com/problem/content/description/1915/ 中等 枚举、前缀和、哈希表 求两个种类数量相等的连续最长区间：可以想到用前缀和来做，两个种类，一个为$1$，一个为$-1$。 求同一种类的连续最长区间：类似于双指针，两个指针$last$和$i$，$i$一直递增
子数组异或和 https://www.acwing.com/problem/content/description/4510/ 中等 哈希表、异或和 题目要求统计数组中满足长度为偶数且前一半异或和等于后一半异或和的非空连续子数组数量。本质是求偶数长度子数组的异或和为 0 的情况。通过异或前缀和的性质，可快速计算任意子数组的异或和，并借助两个哈希表分别记录奇数索引和偶数索引的前缀和出现次数，从而统计满足条件的子数组数量。
异或前缀和的性质。s[i]=s[i−1]⊕a[i] > a[l]⊕a[l+1]⊕…⊕a[r]=s[r]⊕s[l−1]

BFS DFS

题目名称 题目链接 难度 标签 备注
拖拉机 https://www.acwing.com/problem/content/2021/ 中等 双端队列广搜、最短路 边权只有 0 和 1 的最短路问题：适用于边权只有两种情况（0 和 1）的特殊图。双端队列广搜的核心思想：使用双端队列代替堆优化 Dijkstra 算法：当边权为 0 时，将新点加入队头。当边权为 1 时，将新点加入队尾。每个点出队时只处理一次，但可能多次入队以更新最小权值。
正方形数组的数目 https://www.acwing.com/problem/content/description/4522/ 中等 DFS、全排列、剪枝 在全排列问题中，为避免重复解，针对相同数字需要排序后剪枝，保证相同数字按固定顺序使用，剪枝条件是“当前数字与前一个相同，且前一个未被使用时跳过”。总计复杂度：O(n×n!)，如果 n=10：排列数量达到约 360万，大多数情况下会超时，如果良好剪枝了，就不会了。

图论

题目名称 题目链接 难度 标签 备注
牛奶工厂 https://www.acwing.com/problem/content/description/1473/ 中等 图的遍历、DFS、Floyd传递闭包 寻找有向图的“超级汇点”。（能被所有点走到的点一定是出度为0的点，可爆搜）。也可floyd传递闭包（传递闭包就是对图的可达性关系的扩展，使得如果存在间接路径 a→b→c，则直接添加一条 a→c 的边。）
棋盘覆盖 https://www.acwing.com/problem/content/description/374/ 中等 二分图、匈牙利算法 棋盘模型转化：将棋盘的格子视为图中的节点。 如果两个格子相邻且均可放置骨牌，则用一条边连接这两个格子。 问题转化为：在这个图中，找到最大的二分图匹配。黑色格子和白色格子分别组成图的两个独立集合 U 和 V。只允许连接黑白格子之间的边。
货物运输 https://www.acwing.com/problem/content/4244/ 中等 最短路变种、最短边的最大值 题意： 给定一个无向图，每条边有最大承载能力，要求从节点 1 到节点 n，找到路径中最小边权最大的路径，计算这条路径的最大承载能力。解法： 使用改造的最短路算法，通过优先队列（大根堆）进行松弛操作，不断更新每个节点的最大承载能力。每次松弛时，取当前路径的最小边权作为瓶颈值，选择瓶颈值最大的路径到终点，最终输出最大承载能力capacity[neighbor]=max(capacity[neighbor],min(capacity[node],edge weight))
农场派对 https://www.acwing.com/problem/content/description/1134/ 中等 最短路、反向建边 多对一的最短路≡反向建图一对多的最短路
虫洞 https://www.acwing.com/problem/content/906/ 简单 SPFA、负环 是否有负环即可，别忘把所有点都入队（确保算法可以从图的所有节点出发）
最短距离 https://www.acwing.com/problem/content/description/1490/ 中等 超级源点、Dijkstra 通过引入一个虚拟的超级源点（编号为$0$），连接所有有商店的村庄，且边权为$0$，问题从 查询村庄到最近商店的最短距离 转化为 超级源点到查询村庄的最短距离，从而将多源最短路径问题简化为单源最短路径问题。利用Dijkstra算法，从超级源点出发，计算所有村庄到超级源点的最短距离，这一距离即为村庄到最近商店的最短距离。最终，对于每个查询直接返回预先计算的结果即可，算法高效且逻辑清晰。
图的最大边权的最小值 https://leetcode.cn/problems/minimize-the-maximum-edge-weight-of-graph/ 困难 逆向思维、Dijkstra、最大边权最小的路径 前要：在普通的最短路问题中，“最短路”指的是路径边权和最小的路径。而在这里，“最短路”被重新定义为“路径中边权最大值最小的路径”。在路径代价定义为“最大边权”时，贪心扩展的变成了路径中边权的最大值，每次找当前能访问到的边权最小的边。
题意：题目给定一个由 $n$ 个节点组成的无向图，节点编号为 $0$ 到 $n-1$，图的边由数组 $edges$ 表示，其中每条边为 $(A_i, B_i, W_i)$，表示节点 $A_i$ 和节点 $B_i$ 之间有一条权重为 $W_i$ 的无向边。任务是通过删除一些边，使图满足以下条件：图中所有其他节点必须可以到达节点 $0$。删除边后，图中边的最大权重不超过给定的 $threshold$。每个节点到节点 $0$ 的路径不超过 $threshold$。需要返回满足条件时图的最大边权的最小值。如果无法满足所有条件，返回 $-1$。
思路：等价转换！！
把图中的每条边反向，那么原问题等价于删边之后：
1. 从 0 出发，必须能访问到所有点。
2. 每个点的入度至多为 threshold。（一定能满足 threshold 的要求。）
可以从 0 出发，每次走当前能访问到的边中，边权最小的边，这类似 Dijkstra 求最短路（计算路径边权最大值）。更新规则是：新的路径代价为 max(当前路径的代价, 新的边权)

也可二分边权+DFS
关闭分部的可行集合数目 https://leetcode.cn/problems/number-of-possible-sets-of-closing-branches/description/ 困难 Floyd、二进制枚举 **题意：**给定一个公司在全国的 $n$ 个分部以及它们之间的道路信息 $roads$，每条道路由 $[u_i, v_i, w_i]$ 表示连接了 $u_i$ 和 $v_i$ 的一条长度为 $w_i$ 的无向道路。需要关闭一些分部，满足以下条件：
剩余的分部之间必须两两互相连通。
剩余分部的任意两点之间的最远距离不能超过 $maxDistance$。
要求计算满足上述条件的可行关闭方案的数量。
思路： Floyd 计算全局最短路径:预处理所有分部之间的最短路径。枚举所有可能的关闭方案，每种方案可以用一个长度为 $n$ 的二进制数表示，$1$ 表示分部保留，$0$ 表示分部关闭。对于每种方案：
过滤掉所有不连通的方案。可以使用 DFS 或 BFS 检查连通性。
对于剩余的连通子图，检查是否所有点对之间的最短路径小于等于 $maxDistance$。

数论

题目名称 题目链接 难度 标签 备注
买不到的数目 https://www.acwing.com/problem/content/1207/ 中等 数论、结论题、裴蜀定理 结论：p,q为正整数且互质，那么不能凑出来的最大整数为 p * q - (p + q)
回文日期 https://www.acwing.com/problem/content/468/ 中等 日期、回文串、闰年 根据题目要求生成目标日期集合，如回文日期可以通过构造对称的8位数生成；其次，检查生成的日期是否在题目规定的范围内，通过直接比较完成；最后，校验日期是否有效，依据每月的天数规则判断是否合法，特别是对2月需要额外判断闰年条件（年份是4的倍数且不是100的倍数，或是400的倍数）
航班时间 https://www.acwing.com/problem/content/1233/ 中等 时差、时间换算 秒转小时、分钟、秒的计算方法是：小时由秒数整除3600得到（最后整除的是小时的单位，1小时等于3600秒）。分钟由秒数对3600取模后再整除60得到（剔除小时后只剩分钟和秒，整除60得到分钟）。秒数由秒数对3600取模后再对60取模得到（剔除小时和分钟后剩余的秒数）。
包子凑数 https://www.acwing.com/problem/content/1228 中等 完全背包、裴蜀定理 题目要求计算用 $N$ 种蒸笼容量 $A_i$ 组合出任意包子数量 $X$ 时，有多少个数量是无法组合的。若所有蒸笼容量的最大公约数 $\text{gcd}(A) &gt; 1$，则存在无穷多无法组合的数量，直接输出 $-1$。否则，可通过完全背包的动态规划求解，定义 $dp[x]$ 表示是否能组合出数量 $x$。初始化 $dp[0] = \text{True}$，然后对每种蒸笼容量 $A_i$ 更新 $dp[x]$ 为 $dp[x] \text{ or } dp[x - A_i]$。最后统计 $dp$ 中为 $\text{False}$ 的位置数量，即为答案。
数字根 https://www.acwing.com/problem/content/3452/ 简单 数字根、9 9 的倍数的性质：9 的倍数各个数位上的数字之和是 9 的倍数。 任何一个整数模 9 同余于它的各数位上数字之和。（任意一个整数对 9 取模的结果，等于它的各个数位数字之和对 9 取模的结果。）
上课睡觉 https://www.acwing.com/problem/content/description/4369/ 简单 约数 一个数的约数数量由其质因数分解形式决定，计算公式为 $d(n) = (e_1 + 1) \cdot (e_2 + 1) \cdots (e_k + 1)$，其中 $e_i$ 是质因数的指数。在 int 范围内，约数数量最多的数有约 1600 个，如 720720 这样的高度合成数拥有 240 个约数。通常，大多数整数的约数数量与 $\log n$ 成正相关，但高度合成数可以远高于这一范围。完全平方数的约数数量为奇数，而质数的约数数量仅为 2。
约数之和 https://www.acwing.com/problem/content/description/99/ 简单 约数之和、费马小定理 等比数列求和公式为：对于公比为$q$、首项为$a$、共有$n$项的等比数列，其和为 $S = a \frac{1-q^n}{1-q}$（当$q \neq 1$）；
等差数列求和公式为：首项为$a$、末项为$l$、共有$n$项的等差数列，其和为 $S = \frac{n}{2}(a + l)$；费马小定理为：对于一个质数$p$，如果整数$a$与$p$互质，则有 $a^{p-1} \equiv 1 \pmod{p}$，该定理可用来快速计算模逆元，即 $a^{-1} \equiv a^{p-2} \pmod{p}$
末尾连续0 https://www.acwing.com/problem/content/4952/ 简单 质因子 题目要求统计有多少个正整数 $n$ 满足 $n!$ 的末尾连续 $0$ 的数量恰好为给定的正整数 $m$，并输出所有满足条件的 $n$。某个数的尾部0的个数 = 质因子中2和5的个数最小值，可通过公式 $Z(n) = \lfloor \frac{n}{5} \rfloor + \lfloor \frac{n}{5^2} \rfloor + \dots$ 高效计算其值。由于 $Z(n)$ 是单调递增的，利用二分查找可以找到满足 $Z(n) = m$ 的最小 $n$ 和最大 $n$，从而得到满足条件的所有 $n$。如果区间为空，则不存在满足条件的 $n$；否则输出区间中的所有值，时间复杂度为 $O(\log^2 n)$。
寻找整数 第十三届蓝桥杯省赛 B 中等 同余 题意：找一个不超过 10的17次方 的正整数 n，这个n是除以 2 至 49 后的余数已经是给定了的，求这个正整数最小是多少？
思路：若 $x % m1 = a1$ 且 $x % m2 = a2$，则满足这两个同余条件的数具有周期性，其周期为 $\text{lcm}(m1, m2)$。换言之，如果 $x$ 是一个解，下一个满足该条件的数为 $x + \text{lcm}(m1, m2)$。这一结论可以推广到 $n$ 个同余条件，当模数两两互质时，所有解以模数的最小公倍数 $\text{lcm}(m1, m2, \dots, mn)$ 为周期重复。这一性质广泛应用于中国剩余定理和周期性问题的求解。
K 秒后第 N 个元素的值 https://leetcode.cn/problems/find-the-n-th-value-after-k-seconds/description/ 简单 杨辉三角 **题意：**给定两个整数 $n$ 和 $k$，初始时有一个长度为 $n$ 的数组 $a$，其中所有元素为 1。每经过一秒，数组中的每个元素会被更新为其前面所有元素的和加上自身的值，更新是同时进行的。例如，1 秒后 $a[0]$ 保持不变，$a[1]$ 变为 $a[0] + a[1]$，$a[2]$ 变为 $a[0] + a[1] + a[2]$。最终返回 $k$ 秒后数组中最后一个元素 $a[n-1]$ 的值，并对 $10^9 + 7$ 取余。
思路：把脑袋往左斜 45°，就成了下面的杨辉三角。经过 $k$ 秒的更新后，数组中第 $n-1$ 个元素的值可以表示为杨辉三角第 $n+k-1$ 行的第 $n-1$ 个元素，即组合数 $C(n+k-1, n-1)$。这是因为每次更新数组时，相当于构造了杨辉三角的一层，而数组的最后一个元素始终对应当前构造层的最后一个元素。
第 0 行: [1]
第 1 行: [1, 1]
第 2 行: [1, 2, 1]
第 3 行: [1, 3, 3, 1]
第 4 行: [1, 4, 6, 4, 1]

并查集

题目名称 题目链接 难度 标签 备注
交换瓶子 https://www.acwing.com/problem/content/1226/ 中等 贪心、并查集、排列还原 可以贪心暴力，也可并查集找环找规律（证明交换次数为$n - k$，k为环的个数，建图方式为，自己和自己该在的地方存在的数相连）
糖果传递 https://www.acwing.com/problem/content/description/124/ 中等 环形纸牌均分问题、中位数 P2512 [HAOI2008] 糖果传递，首先碰见环，先想到破环成链，枚举断点。此题可推公式，并转换为货仓选址问题，也就是选出中位数。（首先计算所有糖果的总数，并求出每个人应该获得的目标糖果数，然后计算每个人当前糖果数与目标糖果数的差值构成差值数组，再通过累积这些差值构造累积和数组，累积和反映了糖果的盈亏状态。为了使传递代价最小，我们需要调整累积和数组中的值，使其尽可能平衡，根据数学性质，最小绝对差总和对应于累积和的中位数。）
修改数组 https://www.acwing.com/problem/content/1244/ 中等 并查集、树状数组、二分、并查集单链表 题意：题目要求通过依次修改数组中的每个元素，消除数组中的重复整数。修改规则是：如果当前数字在前面的部分已出现，则加 1，直到它不再重复。最终计算出数组中没有重复整数的状态。答案：将前面枚举过的元素用一个集合来表示，集合的根元素是集合所有元素的最大值

ST表（RMQ）

预处理从初始化开始，第一层直接存储原数组，每一层的区间长度逐步翻倍，从 $2$ 开始，每次合并上一层中两个相邻区间的结果构造新层。遍历范围用 $n - 2 \times i + 1$ 保证区间不越界，每次用聚合函数（如最小值、最大值或位运算）合并左区间和右区间的值。最终，通过多层递归构建一个完整的 Sparse Table，时间复杂度为 $O(n \log n)$。记住关键点：“第一层是原数组，区间翻倍递归合并，右端防越界，层层叠加完成表”。

题目名称 题目链接 难度 标签 备注
选数异或 https://www.acwing.com/problem/content/description/4648/ 困难 DP、ST、异或、离线莫队 题意：给定一个长度为 $n$ 的数组 $A = [A_1, A_2, \dots, A_n]$ 和一个非负整数 $x$，同时给定 $m$ 次查询。每次查询提供一个区间 $[l, r]$，需要判断在该区间内是否存在两个不同的数，使得它们的异或值等于 $x$。
思路：问题可以简化为：对于每个区间 $[l, r]$，判断是否存在一个数 $A[i]$ 和一个数 $A[j]$，其中 $A[j] = A[i] \oplus x$，且它们在这个区间内。（对于每个查询 [l,r]，判断是否存在两个数 A[i],A[j] 满足：A[i]⊕A[j]=k，等价于：A[j]=A[i]⊕k）。
为此，我们构建一个辅助数组 $w[i]$，表示 $A[i] \oplus x$ 最近一次出现的下标（若不存在则为 $0$）。然后通过预处理 $w[i]$ 的最大值，使用 ST 表在 $O(1)$ 时间内快速查询区间 $[l, r]$ 中 $w[i]$ 的最大值。如果最大值 $\geq l$，说明区间内存在满足条件的两个数，返回 "Yes"；否则返回 "No"。通过 ST 表的构建和查询，总复杂度为 $O(n \log n + m)$
重点！也可用莫队来做，但是Python的复杂度高
子数组按位与值为 K 的数目 https://leetcode.cn/problems/number-of-subarrays-with-and-value-of-k/description/ 困难 DP、ST、二分 题意：给定一个整数数组 $nums$ 和一个整数 $k$，需要返回满足条件的子数组个数，其中每个子数组中所有元素按位与（AND）的结果等于 $k$。
思路：利用稀疏表（Sparse Table）和二分查找的方法。稀疏表可以高效地求解子数组范围内的按位与结果，而二分查找则用于定位符合条件的子数组范围
1. 使用稀疏表 $st$，预处理数组 $nums$，以支持快速区间查询。
2. 由于按位与的结果是单调非递减的，取负号后变为单调非递增，可结合 Python 的 bisect_left 和 bisect_right 函数在索引范围 $[i, n)$ 上进行二分查找。key=lambda r: -st.query(i, r)：对每个终点 $r$ 计算按位与结果的负值，用于在负数序列中查找 $-k$。
3. 二分查找定位满足按位与结果等于 $k$ 的索引范围 $[l, r)$，累加符合条件的子数组个数。

Trie

题目名称 题目链接 难度 标签 备注
转换字符串的最小成本 II https://leetcode.cn/problems/minimum-cost-to-convert-string-ii/description/ 困难 Floyd、Trie、记忆化搜索 题意：给定两个字符串 $source$ 和 $target$，它们长度相同且由小写字母组成，还有两个数组 $original$ 和 $changed$，以及一个整数数组 $cost$，其中 $cost[i]$ 表示将 $original[i]$ 替换为 $changed[i]$ 的费用。需要通过最小化操作费用将 $source$ 转换为 $target$，并满足以下条件：
1. 不同操作选择的子串不能在 $source$ 中重叠。
2. 相同位置的两次操作必须选择相同的子串。
如果转换不可行，则返回 $-1$。
思路：
1. 字符串转换的最短路径: 使用 Floyd 算法优化字符串距离计算。通过将 $original[i]$ 到 $changed[i]$ 转换表示为图的边，计算所有字符串之间的最短距离。（Floyd优化 if dis[i][k] == inf: continue）
2. 字典树 (Trie): 建立 Trie 结构，用于将字符串转换为整数下标，便于在图中查询。Trie 还支持快速搜索字符串的所有前缀，以找到可替换子串的位置。需要额外判断前缀的合法性并记录每个子串的可能位置。
3. 记忆化搜索: 从字符串的第 0 位开始递归处理，用 DFS 判断当前是否可以替换子串。如果可以替换，则递归处理下一个位置。若子串相同且符合转换条件，则对应最短路径为 $0$，也一并处理。

扫描线、线段树

扫描线

扫描线算法通过右端点偏移映射将区间 ([l, r]) 映射为离散化索引范围 $([X_l, X_{r+1}])$，从而弥补空缺。

modify 函数在更新区间时，通过调用 pushup 函数递归维护当前节点的信息，使父节点与子节点状态保持一致。运用覆盖操作进行pushup，从而覆盖掉该节点下面的曾经存在的操作（因为这个是扫描线，只在乎你操作次数和区间长度）

pushup 的意义在于动态更新线段树节点的覆盖长度 ($len_u$)，如果当前区间被完全覆盖（即 $cnt &gt; 0$），则覆盖长度直接为物理长度 ($X_{r+1} - X_l$)；否则，覆盖长度由左右子节点的覆盖长度相加，即 $(len_u = len_{ls} + len_{rs})$。

扫描线image-20250105194507340

题目名称 题目链接 难度 标签 备注
油漆面积 https://www.acwing.com/problem/content/description/1230/ 中等 扫描线、线段树 发现规律并找环

模版题目

题目类型 题目名称 备注
归并排序 https://www.acwing.com/problem/content/description/789/
区间合并 https://www.acwing.com/problem/content/805/
第k个数 https://www.acwing.com/problem/content/788/ 快速选择（Top K 问题，也可通过堆来做)
逆序对的数量 https://www.acwing.com/problem/content/790/ 逆序对问题：归并、树状数组板子（动态前缀和）、权值线段树（权值线段树在求解逆序对时，将数组中的元素值映射到离散化后的权值范围，并通过构建线段树对权值进行动态更新和查询。与普通线段树相比，权值线段树的关键区别在于其节点的意义不同——普通线段树通常维护一个区间上的某种值（如和、最值），而权值线段树关注权值范围内的动态统计信息，如出现次数或前缀和。）思路：先将数组离散化，将原数组元素映射到一个有序数组的位置（权值范围）。随后从头到尾依次遍历原数组，每次查询当前元素的权值右侧（比当前元素大的值）的累积和，累积和即为当前元素对应的逆序对贡献。查询完成后，将当前元素的权值更新到线段树中
浮点二分 https://www.acwing.com/problem/content/792/
KMP https://www.acwing.com/problem/content/description/833/
树的重心 https://www.acwing.com/problem/content/description/848/ 树的DFS、树的重心（重心是让分割后最大的子树尽可能“小”的那个节点。）
Bellman-Ford https://www.acwing.com/problem/content/855/ 有边数限制的单源最短路，检测负权回路（如果某条边还能更新，则存在负权回路。）
单调栈 https://www.acwing.com/problem/content/832/ 给定一个序列，求每一个数的左边离他最近的（最小/最大）数是什么
完全背包问题 https://www.acwing.com/problem/content/3/ 优化后的式子和01一样，第二层枚举顺序相反
多重背包问题 https://www.acwing.com/problem/content/4/ 二进制倍增优化，n 种多重背包物品被转换为 cnt（被二进制倍增拆分出来的物品的总数量） 个 01 背包物品。
最短编辑距离 https://www.acwing.com/problem/content/904/ LIS模型
石子合并 https://www.acwing.com/problem/content/284/ 区间DP板子
求组合数 III https://www.acwing.com/problem/content/889/ 组合数、Lucas
卡特兰数 https://www.acwing.com/problem/content/891/ 卡特兰数: $Cat(n) = C(2n, n) - C(2n, n - 1) = \frac {C(2n, n)} {n + 1} = \frac {(2n)!} {(n + 1)!n!}$。括号匹配问题： 给定 n 对括号，求合法括号序列的总数。二叉搜索树： 给定 n 个节点，能构造的不同二叉搜索树的总数
最短Hamilton路径 https://www.acwing.com/problem/content/293/ 题意：给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。状态压缩dp，遍历所有可能的状态 i，dpi：表示从起点 0 出发，经过状态 i 表示的顶点集合，最终停留在顶点 j 的最短路径长度。
树的直径 https://www.acwing.com/problem/content/1209/ 树上最长路——树的直径，首先，任选一个节点作为树的根，将树转化为有根树。通过 DFS 从底向上递归计算每个节点的最长向下路径，设 dp[u] 表示从节点 u 出发的最长路径长度。对于每个节点 u，找到其子树中两条最长路径，计算经过 u 的路径长度为两者之和，并更新全局直径。在递归返回时，将最长的一条路径长度作为 u 的结果返回给其父节点。整个过程的时间复杂度为 O(n)。