由于我使用的 oj 平台比较杂，很多时候找不到自己做过的题。
特此将有价值的题目分类索引。
本分类从 2025.01 开始。
记忆化搜索 #
leetcode 63.不同路径 - 经典走迷宫记忆化搜索
leetcode 132. 分割回文串 Ⅱ - 分割字符串，返回计数。此题做法先记忆化搜索来预处理子串，之后用简单的 选或不选 DP 进行分割。
蓝桥 火车运输 - 完全背包的扩展，但用记忆化更简单点。核心剪枝的是当找到一个最优状态直接终止程序，基本上算是个猜结论题。
leetcode 3509. 最大化交错和为 K 的子序列乘积 - 完全背包的扩展。但需要对后缀零进行分类讨论，并在搜索前剪枝。
leetcode 416. 分割等和子集 - 记忆化搜索 + 剪枝。选或不选使得两个子集相等，有较多的剪枝技巧。
蓝桥 划分 - 和 LC416 非常相似，当两个子集相等时取答案。注意要直接当已经相等时直接剪枝，进而才能在合理时间内结束。
leetcode 474. 一和零 - 两个维度的 01 背包
搜索 #
leetcode 90 - 类似选或不选的简单搜索
leetcode 680 - 经典题验证回文串
leetcode 131 - 经典回溯法，分割字符串
leetcode 1863. 找出所有子集的异或总和再求和 选或不选的搜索，注意”异或操作“并不能直接累计
HOT100 22. 括号生成 - 虽然在回溯的提单，但其实只需要可以在搜索过程中剪枝即可
蓝桥 不同的总分值 - 最简答的选或不选搜索
回溯 #
HOT100 46. 全排列 - 经典搜索回溯问题
HOT100 78. 子集 - 经典搜索回溯问题
HOT100 17. 电话号码的字母组合 - 哈希表 + 基础回溯
HOT100 39. 组合总和 - 对结果查重的回溯问题，需要注意分割数组
HOT100 79. 单词搜索 - 走格子回溯路径，注意剪枝。优化：词频判断提前返回
HOT100 131. 分割回文串 - j 从 i 起枚举子串终点，判断是否回文，若是则加入路径并递归，完成后回溯。
HOT100 51. N 皇后 - 经典题 N 皇后，回溯列剪枝，对角线检测，构造棋盘输出结果。
动态规划 #
资源分配 DP #
leetcode 2209 用地毯覆盖后的最少白色砖块 - 资源分配问题，dp[i][j]表示：前 i 个地砖用 j 个地毯后的最小白砖数量。其中 i 为进度轴、j 为资源轴。
leetcode 1278. 分割回文串 III - 是前面两个记忆化搜索的分割字符串的延续。思路还是资源分配 DP，前 i 给字符分割成 j 给字符串的最小修改次数。
leecode 1745. 分割回文串 IV - 和上面的 Ⅲ 几乎完全一致，不过是把维护修改数量改成维护 bool 值。
区间 DP #
奶牛体检 - 区间DP + 前缀和，比较规矩的模板
leetcode 1690. 石子游戏 VII - 区间DP + 前缀和，需要将博弈转化到递归，进而想到重复子问题。
luogu P1005 - 区间DP (记忆化版)，此题要处理大数输出。
打家劫舍型 DP #
蓝桥 松散子序列 - 打家劫舍板子，一种做法 dp[i][1] 表示 i 选了的最大值 dp[i][0] 表示 i 没选的最大值，空间优化做法为 dp[i] 就表示当前最大值
蓝桥 对局匹配 - 将数值分成 k 组，其中 i+k，i+2*k……为一组，可以保证组之间互不干扰。而在组中，就是打家劫舍问题。
leetcode 2597. 美丽子集的数目 - 和上面的对局匹配几乎完全一致，不过要多想一下为什么 k 组之间相互独立
leetcode 2140. 解决智力问题 - 打家劫舍变形，从左往右刷表法。每次维护的是 x + dx 下标的值、
leetcode 3557. 不相交子字符串的最大数量 - 本质上还是选或不选问题，不过需要用 O1 维护该数的前一个相同数的位置，并保证 i - j >= 3。当然也可能直接双指针贪心，最小的分割情况就是最好的。
状态机 DP #
leetcode 2272. 最大波动的子字符串 - 此题转化成 状态机DP 的难度不低，小写字母双层外部遍历，内部遍历中维护两个状态。
leetcode 2712. 使所有字符相等的最小成本 - 状态机 DP 板子，也可以用贪心做（但有点难想到）。
蓝桥 蜗牛 - 二维状态 DP，几乎是板子了
蓝桥 翻转 - 看懂题就是很简单的状态机
蓝桥 贸易航线 - 线性 DP 部分非常简单，几乎就是最基础的维护前缀最大 DP。但数据预处理比较麻烦，即将题目的数据转化为 DP 直接能用的（价值、所需持续时间）二元组，题解中也有更优雅的不需要预处理的办法，此外也需要贪心发现 k 不影响买卖。
经典线性 DP #
leetcode 72. 编辑距离 - 最长公共子序列板子。
leetcode 368. 最大整除子集 - 思路与最长上升子序列完全一致，需要维护具体的序列内容（而非标准的长度）
leetcode 300. 最长递增子序列 - 经典题：最长上升子序列。nlogn 是二分查找的做法
状压 DP #
蓝桥 羊圈 - 状态压缩 DP 的板子。其中 i 表示遍历到第几头羊，j 用状态压缩的二进制表示用了哪些羊圈，此题用了记忆化。
博弈 DP #
leetcode 913. 猫和老鼠 - 比较复杂的博弈，写了博客文章。
蓝桥 砍柴 - 基本是最简单的博弈，记忆化和递推都好写。加一个线性筛判断质数，但这题卡常极其恶心。
蓝桥 魔法迅游 - 比较复杂的状态机 DP，也包含了前缀优化 DP 的思路。状态转移很复杂，模拟量较大。
数位 DP #
leetcode 1012. 至少有 1 位重复的数字 - 先导零 + 掩码
leetcode 2719. 统计整数数目 - 数位 DP 板子，无先导零
leetcode 233. 数字 1 的个数 - 最基础的数位 DP，无先导零
leetcode 600. 不含连续1的非负整数 - 简单数位 DP，无先导零，用一个 pre 存储上一个位置的数字。且此题是二进制串。
leetcode 2376. 统计特殊整数 - 需要考虑掩码和先导零
蓝桥 奇怪的数 - 数位 DP 过 60%，后 40% 卡内存。正解是将 pos 转为奇或偶两种状态的五维 DP。
leetcode 2999. 统计强大整数的数目 上下界数位 DP，不用考虑先导零。判断后缀在状态转移方程中，如果 pos 到达后缀的位置，则只能在范围内选择后缀的数字。
其他 DP #
蓝桥 选数异或 转化任务为 O1 查找区间内是否存在 x。但区间长度最多支持 On，因此将问题在此转化为：以 r 为基准维护最短失败区间长度。而这步需要 ：维护 r 前最近的 x 位置（哈希表），如果 x 位置在区间外，则延续当前最短失败区间（状态转移方程）。想到这步之后就是基本的线性 DP 了。
前缀和 & 差分数组 #
leetcode 3070. 元素和小于等于 k 的子矩阵的数目 - 二维前缀和板子。
ccfcsp 坐标变换（其二） - 前缀和 + 模拟，注意下三角函数库函数输入为弧度制。并需要控制输出精度。
leetcode 3355. 零数组变换 I - 差分数组板子，最后有一个小贪心。
蓝桥 等差数列 - 给一个少了 n 个元素的数列，给出完全包含其全部元素的等差数列。说是差分数组，实际只是排序后记录临近差值，然后求全部 gcd。
HOT100 560. 和为 K 的子数组 - 前缀和 + 两数之和，也可以滑动窗口。用哈希表记录每一个前缀和，如果能和当前的前置和组成
HOT100 53. 最大子数组和 - 当前最大的前缀和减去最小的前缀和就是答案。（也可以更优雅的分治法）
HOT100 238. 除自身以外数组的乘积 - 前缀后缀积，如果想控制 O1 空间复杂度，可以只维护 suf 数组和一个 “当前 pre”。
堆 & 栈 & 队列 & 桶 #
栈 #
leetcode 3561. 移除相邻字符 栈的应用，这题其实和括号匹配一个意思
懒删除堆 #
3092. 最高频率的 ID - 懒删除堆，实际上是哈希表加堆。
top K #
leetcode 215. 数组中的第K个最大元素 topK 板子。我经常错写为把 k 弹出再压入，实际上是当 pq 的长度大于 k 时应该直接弹出旧的并压入新的。
蓝桥 选段排序 贪心 + topK：贪心可知，最优排序区间中至少有一段点是 p 或 q（这个贪心并不好想），因此问题转化为 p->n 和 q->0 的 topk 问题。
单调队列 #
HOT100 239. 滑动窗口最大值 - 滑动窗口维护单调递减队列板子题，用于 On 时间内查找窗口最值
单调栈 #
leetcode 3542. 将所有元素变为 0 的最少操作次数 - 贪心加单调栈，要从概念出发慢慢推出单调栈，思维难度不低。
桶 #
蓝桥 限流器 - 经典桶（哈希）应用，对区间整除后加入桶中
滑动窗口 #
HOT100 3. 无重复字符的最长子串 - 板子中的板子，尽量背诵
HOT100 438. 找到字符串中所有字母异位词 - 定长滑动窗口，比普通的简单些。
HOT100 76. 最小覆盖子串 - 滑动窗口板子，多写一个哈希判断字串是否在窗口中即可。
leetcode 3306. 元音辅音字符串计数 II - 至少型 滑动窗口，题目要求恰好 k，但滑动窗口只能解决至少 k 和 至少 k + 1，则需要将其相减。此外可以参考下其求至少的思路，即 ans += l ，其中 l 左侧每个都可以成为一个满足条件的子数组。
蓝桥 特殊的数组 - 逆向滑动窗口，维护的是窗口外的 cnt，用一个 num 记录当前还有几个数不符合要求，从而避免反复查询 cnt
字符串 #
leetcode 541 - 字符串反转、练习下切片
蓝桥 吊坠 - 字符串破坏成链DP + 克鲁斯卡尔 能过 80%，优化常数能过 90%。想过 100% 需要后缀自动机
leetcode 2109. 向字符串添加空格 - 字符串切片
数论 #
快速幂 #
leetcode 1922. 统计好数字的数目 - 快速幂板子
质数筛 #
leetcode 2614. 对角线上的质数 - 线性筛预处理
leetcode 3556. 最大质数子字符串之和 - 直接判断质数，当查询量小时，直接判断比筛更快
组合数学 #
蓝桥 2023 - 组合数学 + 容斥定理。comb 部分用逆元法，容斥定理部分为二项式反演。
蓝桥 困局 - 思维量较高才能发现组合数公式，此外还需与对每种 k 进行枚举其加权。
leetcode 3558. 给边赋权值的方案数 I - 两个步骤：1. 遍历树的最深深度 2. 求该深度个数中（每个数都是1或2），一共有多少种总长度奇数的路径，因此可以用组合数学求和。其中求和 1 个奇数、3个奇数 …… 的组合数，根据二项式定理，就是 2 ^ (i - 1) 种。
质因数 #
蓝桥 儿童数 - 利用唯一分解定理（每个正整数可以唯一表示为若干个质数的幂的乘积）将 1~2024 所有整数质因数分解，统计所有质因数总次数，若某质因数次数 ≥61，则按次数 //61 +1 参与组合乘积。
图论 #
搜索 #
leetcode 547. 省份数量 - 最基础的图论 DFS。
leetcode 1311. 获取你好友已观看的视频 - 最基础的图论 BFS，加一个 map 转化 vector 用 lambda 排序。
leetcode 1129. 颜色交替的最短路径 - 必须交替走两种颜色的路径，由于路径长度都为一，因此还是 BFS。不过要维护两种颜色的 visited 和 两种颜色分别作为第一步的 ans。
蓝桥 走方格 比较板子的走迷宫 BFS，但题目描述和样例都很烂，没有大样例的 debug 需要花一段时间。
HOT100 200. 岛屿数量 - 最基础的 BFS
HOT100 994. 腐烂的橘子 - 同样基础的 BFS
蓝桥 马与象 - 双向 BFS，从马和象分别进行 BFS ，得到其和每个点的 DIS。找所有点中两者的最小距离。
拓扑排序 #
HOT100 207. 课程表 - 判断是否有环，可以拓扑排序或 DFS
leetcode 1462. 课程表 IV - 拓扑排序。维护一个 dp 数组，拓扑排序时，已确认 node 是 next 的先导。则状态转移方程：dp[i][next] = dp[i][next] || dp[i][node]。其中dp[i][j] 表示 i 是 j 的先导。
leetcode 685. 冗余连接 II - 基环树 + 分类讨论。需要的算法是判断入度和判断环，都是基于拓扑排序。
leetcode 2360. 图中的最长环 - 由于每个节点最多一个出边。因此不存在嵌套的环，每个节点至多在一个环中。拓扑排序：找到在环中的节点 + DFS：遍历每个环。
leetcode 3543. K 条边路径的最大边权和 - 先拓扑排序判断有向图顺序，在根据排序进行 DP。状态 dp[i][j] 表示 终点在 i 点、经过 j 条路径的全部可能的总长度大小。通过拓扑排序可以保证只需要遍历一轮 n。或者使用记忆化搜索更加简单。
leetcode 1857. 有向图中最大颜色值 - 拓扑排序 + 图上 DP，拓扑排序判断环，并顺便完成 DP 状态的更新。dp[v][c] 表示以 v 为终点，颜色 c 的最大数量 ，当然也可以 DFS 记忆化搜索。
最短路 #
leetocde 743. 网络延迟时间 - spfa 和 dijk 都写了。
leetcode 1514. 概率最大的路径 - dijk 做法。
leetcode 2642. 设计可以求最短路径的图类 - spfa 做法。
leetcode 3341. 到达最后一个房间的最少时间 I - 经典网格图 dijk
leetcode 3342. 到达最后一个房间的最少时间 II - 网格图最短路，由于需要判断当前 dis 和 dis_num 因此不太适合 BFS。此题我用了 SPFA，会卡常数。网格图这种稠密图更适合 Dijk。
leetcode 1334. 阈值距离内邻居最少的城市 Floyd 多源最短路。
leetcode 3552. 网格传送门旅游 - 01BFS，实际上是将 queue 换成双端队列，不消耗步数就插入队列顶部，也可以视作只有01距离的 dijk
最小生成树 #
蓝桥 吊坠 - 字符串破坏成链DP + 克鲁斯卡尔 能过 80%，优化常数能过 90%。想过 100% 需要后缀自动机。此题用图论的并查集克鲁斯卡尔。
leetcode 1584. 连接所有点的最小费用 克鲁斯卡尔板子。
并查集 #
leetcode 3551. 数位和排序需要的最小交换次数 - 排序最小交换次数问题，实际上就是寻找数组中的连通块数量（将下标视作链表），找连通块可以用 BFS DFS 并查集等等。
LCA #
蓝桥 彩色二叉树 - 完全二叉树的两点 LCA，倍增法的缩减版。用树上两点距离 x y，存储所有标记操作。遍历标记操作，找 x y 距离小于 y 并最晚标记的颜色。 理论复杂度较高，但实际能过全部数据。
leetcode 1123. 最深叶节点的最近公共祖先 - 也可以不用 LCA 做，但可以练一下
leetcode 3559. 给边赋权值的方案数 II - 用倍增法 LCA 求两节点距离，后续的组合数学部分见 3558 题。
前缀树 Trie #
HOT100 208. 实现 Trie (前缀树) - Trie 树板子，构造题
链表 #
比赛很少考，面试经常考
CSP 十滴水 - 递归加双向链表模拟即可。实际上 map 的底层是红黑树，能够实现 log 级别模拟双向链表 ，因此可以直接用 map 逃课。
HOT100 142. 环形链表 II - 快慢指针找入环的第一个节点，技巧题。当快慢指针第一次相遇时候，将快指针重新回到头节点，快慢同步走，再次相遇就是环入口。
线段树 #
leetcode 2080 - 统计区间内数字频数，将静态线段树板子的 max 改成统计词频的哈希表即可。（此题二分 + 前缀和更优）
leetcode 307 - 经典的区间和检索，静态线段树板子
leetcode 1438. 绝对差不超过限制的最长连续子数组 - 区间线段树 + 滑动窗口，CPP 能过，python 卡常。更好的解法是单调队列
模拟 #
蓝桥 连连看 - 需要先简单转化一下，得到模拟所有主副对角线，之后哈希统计。转化稍微需要一点思维。
leetcode 2711. 对角线上不同值的数量差 - 简单二维模拟，用个 set 就秒了
ccfcsp 矩阵计算 - 模拟矩阵的点乘和积乘，此题正常算的复杂度很勉强。矩阵计算需要把点乘放到最后，因此用乘法交换律从右向左算。
蓝桥 交易账本 - 中高强度的模拟，幸好样例给的不错
leetcode 838. 推多米诺 - 小模拟多米诺骨牌，用 BFS 能减少分类讨论
leetcode 1007. 行相等的最少多米诺旋转 - 小模拟找最小
leetcode 2131. 连接两字母单词得到的最长回文串 - 分类讨论，分别模拟自身是回文串的数量、能分别组成回文串的左右字串、最中间可以放一个回文串。
HOT100 73. 矩阵置零 - 模拟，要找节约内存的最优解。用第一行和第一列的来记录本行或列是否要归零。用 bool 记录第一行或列自己是否要归零
HOT100 54. 螺旋矩阵 - 纯模拟，右下左上的顺序
HOT100 48. 旋转图像 - 纯模拟 先换主对角线 再换左右 就是向右选择 90°
蓝桥 记事本 - 经典模拟 vim，易错切片的区间边界问题。值得注意的是，切片的时候 ans[:max(index - n, 0):] 经常容易忘掉下边界最小为零。
日期模拟 #
蓝桥 神奇闹钟 - 日期时间模拟，考库函数。日期做差。
蓝桥 跑步 - 日期时间模拟，注意 weekday() 下标从 0 开始。
蓝桥 跑步计划 - 日期时间模拟，和上一道题十分相似
思维题 #
leetcode 1287. 有序数组中出现次数超过25%的元素 - 有序数组中找 1/4 以上的连续数。其logn 复杂度下，思想角度类似鸽巢原理，或者从字符串角度看有一点像 kmp。
蓝桥 召唤数学精灵 - 杯特有的找规律，不得不品尝。前面位置的题不会了就缩小数据范围找规律试试。
蓝桥 数字诗意 - 还是那个找规律，答案是所有的 2 ** n ，用 n & (n - 1) == 0 判断
蓝桥 村的真相 - 稍微难一点的找规律，和考公题一样。
蓝桥 子树的大小 - 思维 + 完全 N 叉树概念了解即可。之后通过遍历最左和最右节点来进行求和。
蓝桥 阶乘的和 - 将阶乘和数组，模拟从最小因子开始合并，若可整除则升级，贪心推进求出最终最大因子值 （需要一点点 gcd 的知识）
leetcode 781. 森林中的兔子 - 思维题：如果同种兔子数量不大于他所说的个数，则有 i+1 种兔子，如果大于，则进行分组即可。
leetcode 2145. 统计隐藏数组数目 - 找最小最大，中间相隔的就是能放下的距离
leetcode 790. 多米诺和托米诺平铺 - 排方块找规律，规律有难度。标注的考思维量的题。
HOT100 169. 多数元素 - 找数组中数量大于 n // 2 的数。法1：当作 LC1287 的弱化版，排序后下表 n // 2 就是答案。法2：时间On，空间O1 摩尔投票法，不太好理解，尤其证明 candidate 需要仔细看。
HOT100 31. 下一个排列 - 经典下一个排序算法，需要两次从后向前遍历找两个下标，交换后反转降序数组。
HOT100 56. 合并区间 - 区间排序后，重叠则合并，不重叠则加入结果。
HOT100 189. 轮转数组 - 最优解法是：reverse(0, n - 1) ; reverse(0, k - 1); reverse(k, n - 1)
HOT100 41. 缺失的第一个正数 - 利用交换将正数放入对应下标，最终首个不匹配位置即为缺失的最小正整数。
HOT100 240. 搜索二维矩阵 II - 最优解法是将其视作一根以右上角为顶点的二分查找树，时间复杂度是 O(m + n)
哈希 #
HOT100 1. 两数之和 - 哈希表的 find 或者默认值设置两种语法
HOT100 49. 字母异位词分组 - 注意下简洁写法的哈希语法
HOT100 128. 最长连续序列 - 用集合判断连续序列起点，元素最多遍历两次。
双指针 #
leetcode 680 - 经典题验证回文串
HOT100 287. 寻找重复数 - 将数组下标的映射视作链表，之后就与快慢指针找环入口一致
HOT100 75. 颜色分类 - 荷兰国旗，双指针。从前向后的指针好理解，但从后向前的指针需要 while，进而在数组原地交换。
HOT100 283. 移动零 - left 表示非零的已经好的位置，right 遇到非零就和 left 交换
HOT100 11. 盛最多水的容器 - 因为面积由 min(height[l], height[r]) 决定，因此先挪更短指针一定是最优解
HOT100 15. 三数之和 - 思路先排序，遍历 i 作为基准，之后 l r 双指针。如果 l 和 r 的 sum 大于目标，则减小 r，反之增加 l。但此题要求不能重复，因此要去掉重复的 i ，和重复的 j，导致边界条件非常麻烦。
HOT100 42. 接雨水 - 典中典 1. 前缀后缀法：通法，思维量较小。统计每个数的最大前后缀；2. 双指针实际上就说前缀后缀的优化版，核心就是哪侧前或后缀更小，就缩那测 ；3.单调递减栈，找上一个更大的，然后填坑。双指针是最优解，前缀后缀和单调栈更常用
异或和 #
HOT100 136. 只出现一次的数字 - 最基础的异或和，原理 ： a ^ a = 0 ; a ^ b ^ a = b
leetcode 2588. 统计美丽子数组数目 - 巧妙的异或和例子
蓝桥 异或和之和 - 异或和 加 贡献法
贡献法 #
农夫约翰的奶酪块 - 贡献法，三维映射到二维
哞叫时间 - 比较麻烦的模拟，基本方法是：先尝试该某点，获取哈希表计数，撤回对该点的修改
哞叫时间Ⅱ - 在遍历过程中维护三个数组，“遍历右，维护左”
鸽巢原理 #
蓝桥 取模 - 乍一看是中国剩余定理。但实际上是 “反证 + 鸽巢原理”，若模值两两不同，则必为 n % m == m - 1（因为小于 m - 1 的已经被占了），遍历验证是否存在不满足的情况。
二分查找 #
leetcode 1552 - 最大化最小
leetcode 1760 - 最小化最大
leetcode 2594 - 最小化最大，本质上是最小化
leetcode 1283. 使结果不超过阈值的最小除数 - 基础的最小化最大
leetcode 81. 搜索选择排序数组Ⅱ - 经典旋转数组二分，要考虑比较多的边界
leetcode 33. 搜索选择排序数组 - 上一道题的简化版
luogu P1068 - 模拟排序 记得看下字符串输入输出
蓝桥 卡片 - 找规律 + 二分答案。规律和二分都非常好想。
蓝桥 切木棍 - 经典最大化最小，注意切的时候是 (i - 1) / num 即可
贪心 #
leetcode 624 - 经典的遍历右，维护左。
蛋糕游戏 - 博弈中的贪心，要使用到前缀和
leetcode 1328. 破坏回文串 - 有一些贪心做法，不过暴力也能过。
leetcode 2070. 每一个查询的最大美丽值 - 经典遍历右，维护左
leetcode 1963. 使字符串平衡的最小交换次数 - 可以交换的括号匹配，当遇到无法匹配的右括号时，贪心从后向前的左括号交换。
蓝桥 回文数组 - 贪心，前后做差。可以看作差分数组的简化版本。
leetcode 2680. 最大或值 - 贪心，将 k 都给一个元素是最好的。为了 On 实现，需要维护前后缀和。要注意此题并非维护区间和，区间和需要线段树。
leetcode 2116. 判断一个括号字符串是否有效 - 指定可变括号位置的括号匹配。分别将可变的括号视作 “(“ 和 “)”，如果两次匹配都能成功，说明可变的位置是灵活的，说明能成功匹配。
leetcode2874. 有序三元组中的最大值 II - 贪心使得 nums[i] 和 nums[k] 最大，因此只用维护最大前缀后缀即可
蓝桥 最长回文前后缀 - 双指针回文贪心，如果严格复杂度需要马拉车算法，实际上用双指针处理前后缀即可。
蓝桥 三国游戏 - 贪心 + 排序。同一选择只会有一种赢。
蓝桥 球衣号码 - 简单推理可得，编码的最大值只和最小和最大的号有关
面试智力题 #
鸡蛋坠楼 #
leetcode 1884. 鸡蛋掉落-两枚鸡蛋 - 找到所有 n * (1 + n) / 2 即全部累计的数
-
从 n 直接得到次数比较难，类似上一题（k == 2）的特例
可以枚举 i 找其能找的最大楼层，降低难度
-
考虑子问题，关键两个因素是“剩余的尝试次数 i 和剩余的鸡蛋数量 j“
此外其时间复杂度 n * k 为 1e6，更能考虑其 i 与 j 为关键状态
-
在某楼层扔鸡蛋，会产生两种状态
鸡蛋碎了 -> 产生 dfs(i - 1, j - 1) 的子问题 -> 其本身也测出来该楼层正误 -> 获得 dfs(i - 1, j - 1) + 1 的楼层
鸡蛋没碎 -> 产生 dfs(i - 1, j) 的子问题 -> 即该楼层以上能测出多少楼层
该楼层以下 + 该楼层以上 -> dfs(i - 1, j - 1) + 1 + dfs(i - 1, j)
-
当 i == 0 或 j == 0 时测不出来楼层 返回 0
概率论 #
leetcode 1227. 飞机座位分配概率 - 除第一人外，每人坐对概率对称，最终乘客有一半概率坐上自己的座位。