题单汇总

线性DP

前缀和

区间DP

树形DP

状压DP

安卓系统手势解锁
我能赢吗
不同路径 III —— 状态压缩 DP + 记忆化
划分为 k 个相等的子集 —— 状态压缩 DP + 记忆化
访问所有节点的最短路径 —— Floyd + 状态压缩 DP 求最短哈密顿路
最短超级串 —— 状态压缩 DP + DP 过程记录路径
优美的排列
骑士拨号器
参加考试的最大学生数
大礼包
贴纸拼词
按位与为零的三元组

数位DP

满足某些条件的数字个数:
最大为 N 的数字组合
中心对称数 III
计算各个位数不同的数字个数
不含连续 1 的非负整数
至少有 1 位重复的数字
易混淆数 II

将]x∈[L,R] 代到一个函数 f(x) 中, 一个数字 x 的 f(x) 值为一次贡献的量, 求总的贡献:
数字 1 的个数
范围内的数字计数
2 出现的次数

图上DP

1548. 图中最相似的路径
568. 最大休假天数
1340. 跳跃游戏 V
329. 矩阵中的最长递增路径
1048. 最长字符串链

概率DP

1. 分汤
   837. 新21点
   1230. 抛掷硬币
   688. “马”在棋盘上的概率
   1467. 两个盒子中球的颜色数相同的概率
   剑指 Offer 60. n个骰子的点数
   1227. 飞机座位分配概率
   1377. T 秒后青蛙的位置

博弈

(1) 877. 石子游戏 / 486. 预测赢家
minimiax + 区间DP
(2) 1908. Nim 游戏 II
minimax + 状态压缩DP
(3) 375. 猜数字大小 II
minimax + 区间DP
(4) 294. 翻转游戏 II
minimax + 记忆化搜索

翻转游戏
293. 翻转游戏
Nim 游戏
292. Nim 游戏
石子游戏
1140. 石子游戏 II
1406. 石子游戏 III
1510. 石子游戏 IV
井字游戏
348. 判定井字棋胜负
794. 有效的井字游戏
1275. 找出井字棋的获胜者
其它
486. 预测赢家
464. 我能赢吗
1025. 除数博弈
913. 猫和老鼠

作者：FennelDumplings
链接：https://leetcode-cn.com/leetbook/read/dynamic-programming-3-plus/nmwx35/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

随机算法

洗牌
384. 打乱数组
拒绝采样
478. 在圆内随机生成点
470. 用 Rand7() 实现 Rand10()
蓄水池抽样
398. 随机数索引
382. 链表随机节点
加权蓄水池抽样
528. 按权重随机选择
黑名单映射
710. 黑名单中的随机数
519. 随机翻转矩阵
加权随机事件二分
528. 按权重随机选择
497. 非重叠矩形中的随机点

作者：FennelDumplings
链接：https://leetcode-cn.com/leetbook/read/probability-problems/n9844s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

面试

算法和数据结构