教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本文基于 《概率 DP》 一文展开系统梳理「概率 DP」与「期望 DP」的数学根基——样本空间、事件概率、数学期望、全概率公式与全期望公式并给出通用状态转移方程模板。结合 AlgoNote 仓库中 骑士在棋盘上的概率、飞机座位分配概率、抛掷硬币、新 21 点 等题解读者可以掌握「从概率论公式推导 DP 状态转移方程 → 编码实现 → 复杂度分析」的完整解题路径。1. 概率 DP 与期望 DP 是什么概率 DP一类使用动态规划方法来求解概率与期望的问题也可以分别叫做「概率 DP」「期望 DP」。由于概率和期望具有线性性质使得可以在概率和期望之间建立一定的递推关系从而通过动态规划的方式来解决一些概率问题。概率 DP 和期望 DP 的难点主要有两点状态转移方程的推导。这一点和一般动态规划并无太大差别核心仍然是根据阶段划分、状态定义、转移方程、初始条件四要素来建模。概率论知识。这一点涉及到对概率论基础知识的掌握是概率 DP 区别于普通 DP 的关键门槛。其中「概率 DP」对应了概率论知识中的「全概率公式」「期望 DP」则对应了「全期望公式」。也就是说概率 DP 的本质是用动态规划去展开全概率公式期望 DP 的本质是用动态规划去展开全期望公式。下面先补齐这两块概率论基础。2. 概率论基础知识2.1 样本空间、事件和概率基本事件在概率论中我们将一次随机实验中的某个可能结果称为「样本点」或者「基本事件」。样本空间所有可能的结果组成的集合称为「样本空间」标记为 $S$。随机事件样本空间 $S$ 的一个子集 $A$$A \subseteq S$称为「随机事件」。概率对于样本空间 $S$ 中的每一个随机事件 $A$如果都存在一种时间到实数的映射函数 $P(A)$满足$P(S) 1$$0 \le P(A) \le 1$对于两个互斥事件$P(A \cup B) P(A) P(B)$。则称 $P(A)$ 为随机事件 $A$ 的概率。这三条公理规范性、非负性、可加性是所有概率模型的基础。概率 DP 中每个状态取值的合法性判断概率是否在 $[0,1]$ 内、各分支概率之和是否为 $1$本质上都是对这三条公理的检查。2.2 随机变量、数学期望随机变量对于样本空间 $S$ 中的任意事件 $i$都有唯一的实数 $X_i$ 与之对应则称 $X X_i$ 为样本空间 $S$ 上的随机变量。常见的随机变量主要有「离散型随机变量」与「连续型随机变量」。「概率 DP」主要涉及到离散型随机变量——因为 DP 状态天然是离散的棋盘坐标、步数、分数、硬币数量等。数学期望如果随机变量 $X X_i$ 的概率为 $P(X X_i) p_i$则称 $E(x) \sum p_ix_i$ 为随机变量 $X$ 的数学期望。数学期望的一些性质线性函数性质满足$E(aX bY) a \times E(X) b \times E(Y)$如果随机变量 $X$、$Y$ 相互独立那么$E(XY) E(X)E(Y)$。其中数学期望的线性函数性质是我们能够对数学期望进行递推求解的基本依据——正是它保证了子状态的期望可以线性叠加成父状态的期望从而让 DP 递推在期望问题上成立。2.3 全概率公式、全期望公式概率 DP 的理论基础主要是「全概率公式」。全概率公式设 $B_1, B_2, B_3, …, B_n$ 是样本空间 $S$ 中互不相交的一系列事件并且满足 $S \cup_{j 1}^n B_j$那么对于任意事件 $A$有 $$P(A) \sum_{j 1}^{n} P(A \mid B_j)P(B_j)$$「概率 DP」中一般常见的状态转移方程式为$dp[i] \sum_{j 1}^{n} p[i][j] \times dp[j]$。其中 $dp[i]$ 对应全概率公式中的 $P(A)$$p[i][j]$ 对应了 $P(B_j)$$dp[j]$ 则对应了 $P(A \mid B_j)$。与概率 DP 类似期望 DP 的理论基础主要是「全期望公式」。全期望公式设 $X$、$Y$ 为随机变量$E(Y) E(E(Y \mid X)) \sum_{j 1}^n P(x_j) E(Y \mid x_j)$。「期望 DP」中一般常见的状态转移方程式同样写成$dp[i] \sum_{j 1}^{n} p[i][j] \times dp[j]$。其中 $dp[i]$ 对应全期望公式中的 $E(Y)$$p[i][j]$ 对应了 $P(x_j)$$dp[j]$ 则对应了 $E(Y \mid x_j)$。可以看到概率 DP 与期望 DP 的转移方程在形式上完全一致都是当前状态 各分支转移概率 × 子状态值的加权求和。区别仅在于状态值 $dp[j]$ 的语义是概率还是期望。因此掌握全概率公式与全期望公式就等于掌握了这一类 DP 的推导钥匙。3. 通用建模流程四要素分析法结合原文档与仓库题解可以提炼出概率 DP / 期望 DP 的通用建模流程与普通 DP 一样遵循四要素阶段划分按随机过程的推进维度划分例如步数、轮次、已处理的物品数、分数等状态定义$dp[i]$或高维 $dp[i][j]$表示某状态下的事件概率 / 期望状态转移方程列出所有可能的分支转移概率 $p[i][j]$套用模板 $dp[i] \sum_{j} p[i][j] \times dp[j]$ 加权求和初始条件与边界明确零阶段的取值通常为 $1$ 或 $0$并处理越界分支概率为 $0$。一个重要的实践技巧是转移方程写出来后先验证各分支概率之和是否为 1。这是概率模型正确性最直观的自检手段对应概率公理中的可加性。4. 仓库实战四道经典概率 DP 题目精讲原文档给出了两道练习题目仓库 00_06_categories_list.md 的「概率 DP 题目」分类中还收录了更多相关题解。这里选取四道覆盖不同技巧的代表性题目展开。4.1 0688. 骑士在棋盘上的概率概率 DP 入门题目与完整推导见 knight-probability-in-chessboard.md。题目大意在一个n * n的国际象棋棋盘上骑士从单元格(row, column)开始尝试进行k次移动。骑士每次移动会等概率从8种走法走日字中选择一种即使该走法会离开棋盘。求骑士停止移动后仍留在棋盘上的概率。数据范围$1 \le n \le 25$$0 \le k \le 100$。解题思路动态规划阶段划分按照骑士所在位置和所走步数进行阶段划分。状态定义dp[i][j][p]表示从位置(i, j)出发移动不超过p步的情况下最后仍留在棋盘内的概率。状态转移方程骑士有8种走法每种走法被选中的概率为 $\frac{1}{8}$。假设下一步落点为(new_i, new_j)该方向落点仍在棋盘内的概率为dp[new_i][new_j][p - 1]则 $$dp[i][j][p] \sum dp[new_i][new_j][p - 1] \times \frac{1}{8}$$ 这正对应全概率公式所有可能的下一步方向构成了一个完备事件组。初始条件从位置(i, j)出发移动不超过0步一定还留在棋盘内即dp[i][j][0] 1。最终结果dp[row][column][k]。参考代码class Solution: def knightProbability(self, n: int, k: int, row: int, column: int) - float: dp [[[0 for _ in range(k 1)] for _ in range(n)] for _ in range(n)] for i in range(n): for j in range(n): dp[i][j][0] 1 directions {(-1, -2), (-1, 2), (1, -2), (1, 2), (-2, -1), (-2, 1), (2, -1), (2, 1)} for p in range(1, k 1): for i in range(n): for j in range(n): for direction in directions: new_i i direction[0] new_j j direction[1] if 0 new_i n and 0 new_j n: dp[i][j][p] dp[new_i][new_j][p - 1] / 8 return dp[row][column][k]复杂度分析外层三重循环的时间复杂度为 $O(n^2 \times k)$内层directions循环固定执行 8 次可视为常数级故总时间复杂度 $O(n^2 \times k)$空间复杂度 $O(n^2 \times k)$三维数组保存状态。本题的价值在于展示了越界分支直接丢弃概率为 0这一概率 DP 的常规边界处理手法。4.2 1227. 飞机座位分配概率数学归纳 概率递推题目与完整推导见 airplane-seat-assignment-probability.md。题目大意$n$ 位乘客即将登机飞机上刚好有 $n$ 个座位。第一位乘客的票丢了随机选一个座位坐下。其余乘客遵循规则自己的座位空着就坐自己的座位自己的座位被占用就随机选其他座位。求第 $n$ 位乘客坐在自己座位上的概率。数据范围$1 \le n \le 10^5$。解题思路数学 动态规划思想按登机顺序给乘客编号 $1 \sim n$用 $f(n)$ 表示第 $n$ 位乘客坐在自己座位上的概率。$n 1$第 1 位乘客只能坐在第 1 个座位上$f(1) 1$。$n 2$第 1 位乘客有 $\frac{1}{2}$ 概率选中自己的位置此时第 2 位乘客一定坐对贡献 $\frac{1}{2} \times 1.0$有 $\frac{1}{2}$ 概率坐在第 2 位乘客的位置上此时第 2 位乘客一定坐错贡献 $\frac{1}{2} \times 0.0$。故 $f(2) \frac{1}{2} \times 1.0 \frac{1}{2} \times 0.0 0.5$。$n \ge 3$分三类讨论第 1 位乘客的落座以 $\frac{1}{n}$ 概率坐在自己位置 → 后续座位不被占第 $n$ 位一定坐对贡献 $\frac{1}{n} \times 1.0$以 $\frac{1}{n}$ 概率坐在第 $n$ 位乘客的位置 → 第 $n$ 位一定坐错贡献 $\frac{1}{n} \times 0.0$以 $\frac{n-2}{n}$ 概率坐在第 $i$ 号座位$2 \le i \le n - 1$→ 问题规模缩小为 $n - (i - 1)$ 的子问题。综合可得递推式$$\begin{aligned} f(n) \frac{1}{n} \times 1.0 \frac{1}{n} \times 0.0 \frac{1}{n} \times \sum_{i 2}^{n-1} f(n - i 1) \cr \frac{1}{n} \left(1.0 \sum_{i 2}^{n-1} f(n - i 1)\right) \end{aligned}$$将 $f(n) \times n$ 与 $f(n - 1) \times (n - 1)$ 两式相减可消去求和项并得到 $f(n) f(n - 1)$。结合 $f(1) 1$、$f(2) 0.5$最终结论为$$f(n) \begin{cases} 1.0 n 1 \cr 0.5 n \ge 2 \end{cases}$$参考代码class Solution: def nthPersonGetsNthSeat(self, n: int) - float: if n 1: return 1.0 else: return 0.5复杂度分析时间复杂度 $O(1)$空间复杂度 $O(1)$。本题展示了概率递推的另一种形态——不一定要层层 DP通过归纳消去求和项后可能得到闭式解。这也是概率 DP 题状态转移方程推导难度之所在。4.3 1230. 抛掷硬币概率 DP 滚动数组优化题目与完整推导见 toss-strange-coins.md。题目大意给定数组prob其中prob[i]表示第i枚硬币正面朝上的概率同时抛掷所有硬币求恰好有target枚硬币正面朝上的概率。数据范围$1 \le prob.length \le 1000$$0 \le prob[i] \le 1$。解题思路动态规划与 0-1 背包同构阶段划分依次处理每枚硬币与背包问题非常相似。状态定义dp[j]表示处理到当前硬币时恰好有j枚硬币正面朝上的概率。状态转移方程对第i枚硬币正面概率为p正面朝上dp[j] dp[j-1] × p反面朝上dp[j] dp[j] × (1-p)合并即 $dp[j] dp[j] \times (1-p) dp[j-1] \times p$。初始条件dp[0] 1未处理任何硬币时 0 枚正面的概率为 1其余为 0。最终结果dp[target]。空间优化滚动数组仿照 0-1 背包从后向前更新避免覆盖上一轮的状态for j in range(min(i, target), 0, -1): dp[j] dp[j] * (1-p) dp[j-1] * p dp[0] * (1-p)完整实现内层从target倒序dp[j-1]引用的是上一轮的值不会被覆盖class Solution: def probabilityOfHeads(self, prob: List[float], target: int) - float: dp [0.0] * (target 1) dp[0] 1.0 for p in prob: for j in range(target, 0, -1): dp[j] dp[j] * (1 - p) dp[j - 1] * p dp[0] * (1 - p) return dp[target]复杂度分析时间复杂度 $O(n \times target)$$n$ 为硬币数量空间复杂度 $O(target)$滚动数组优化后。以prob [0.5, 0.5, 0.5], target 0为例逐步走查初始化: dp [1] 第 0 枚硬币 (p0.5): dp[1] 0*0.5 1*0.5 0.5 ; dp[0] 1*0.5 0.5 → dp [0.5, 0.5] 第 1 枚硬币 (p0.5): → dp [0.25, 0.5, 0.25] 第 2 枚硬币 (p0.5): → dp [0.125, 0.375, 0.375, 0.125]最终dp[0] 0.125与三枚硬币全是反面朝上的概率 $0.5 \times 0.5 \times 0.5 0.125$ 一致恰好验证了状态转移方程的正确性。4.4 0837. 新 21 点期望 DP 滑动窗口优化题目与完整推导见 new-21-game.md。题目大意爱丽丝从 0 分开始在得分少于k分时持续抽牌每次从[1, maxPts]中随机等概率获得一个整数累加到分数达到k分或更高即停止。求最终分数不超过n的概率。数据范围$0 \le k \le n \le 10^4$$1 \le maxPts \le 10^4$允许误差 $10^{-5}$。解题思路动态规划 滑动窗口状态定义dp[x]表示从分数为x开始最终得分不超过n的概率。状态转移当x k时游戏停止若x n则dp[x] 1否则dp[x] 0当x k时可抽取[1, maxPts]中任意数字每个数字概率为 $\frac{1}{maxPts}$ $$dp[x] \frac{1}{maxPts} \sum_{i1}^{maxPts} dp[xi]$$优化维护一个滑动窗口和window_sum表示 $\sum_{ix1}^{xmaxPts} dp[i]$使每个状态在 $O(1)$ 时间内完成转移将朴素实现 $O(n \times maxPts)$ 的时间复杂度降为 $O(n)$。参考代码class Solution: def new21Game(self, n: int, k: int, maxPts: int) - float: if k 0 or n k maxPts - 1: return 1.0 dp [0.0] * (k maxPts) # 初始化得分在 [k, n] 范围内已经停止且不超过 n概率为 1 for i in range(k, min(n 1, k maxPts)): dp[i] 1.0 # 滑动窗口和 window_sum min(n - k 1, maxPts) # 从 k-1 倒推到 0 for x in range(k - 1, -1, -1): dp[x] window_sum / maxPts window_sum dp[x] if x maxPts len(dp): window_sum - dp[x maxPts] return dp[0]复杂度分析时间复杂度 $O(n)$空间复杂度 $O(k maxPts)$。本题将概率 DP 与滑动窗口技巧结合是转移方程推导出来后还要做复杂度优化的典型范例。4.5 更多概率 DP 题目00_06_categories_list.md 中「概率 DP 题目」分类还收录了以下题解可作进阶练习题目题解难度0688. 骑士在棋盘上的概率knight-probability-in-chessboard.md中等0808. 分汤soup-servings.md中等0837. 新 21 点new-21-game.md中等1230. 抛掷硬币toss-strange-coins.md中等1467. 两个盒子中球的颜色数相同的概率probability-of-a-two-boxes-having-the-same-number-of-distinct-balls.md困难1227. 飞机座位分配概率airplane-seat-assignment-probability.md中等1377. T 秒后青蛙的位置frog-position-after-t-seconds.md困难LCR 185. 统计结果概率收录于分类列表「概率 DP 题目」中等这些题目覆盖了网格随机游走、指数分布类问题、背包式概率合并、树上随机过程、组合计数 概率等多种概率 DP 形态难度从入门到进阶递进。5. 学习路径小结概率 DP 与期望 DP 是动态规划中理论门槛较高的分支建议的学习路径如下先补概率论基础熟记本文第 2 节中的概率公理、期望的线性性质、全概率公式与全期望公式这是推导一切状态转移方程的公式库再掌握通用模板用第 3 节的四要素流程把题目翻译成 $dp[i] \sum_{j} p[i][j] \times dp[j]$ 的形式并养成检查分支概率之和是否为 1的自检习惯最后刷题巩固从 骑士在棋盘上的概率 入门依次完成 抛掷硬币、新 21 点再挑战 飞机座位分配概率 的数学归纳推导需要复习普通 DP 基础时可回到 动态规划基础 一节或在 08 动态规划目录 中按专题查阅。参考资料【文章】《概率动态规划简介 —— 动态规划图文学树形、图上、概率 博弈动态》LeetBook【文章】《期望动态规划简介 —— 动态规划图文学树形、图上、概率 博弈动态》LeetBook【文章】《浅析竞赛中一类数学期望问题的解决方法》汤可因【文章】《有关概率和期望问题的研究》鬲融【文章】《信息学竞赛中概率问题求解初探》梅诗珂赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐终极概率DP实战指南从基础到进阶的期望值与概率计算问题解析终极概率DP实战指南从基础到进阶的期望值与概率计算问题解析 概率动态规划Probability DP是解决不确定性问题的强大工具广泛应用于游戏策略、风险文档教程知识库TradingAgents-CN 增强数据报告深度解析以平安银行000001为例解读实时行情、历史数据与技术指标的完整数据链路TradingAgents CN 增强数据报告深度解析以平安银行000001为例解读实时行情、历史数据与技术指标的完整数据链路 导读 本文以 Tradin教程文档知识库Vibe-Trading new_share 接口指南3 步拉取 A 股新股上市列表Vibe Trading new_share 接口指南3 步拉取 A 股新股上市列表 Vibe Trading 内置的 Tushare new_share 接人工智能AI Agent金融科技MCP 服务上一篇LinkSwift终极九大网盘直链下载助手彻底告别下载限速困扰下一篇如何用LinkSwift解锁九大网盘真实下载链接终极用户指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考