Dotcpp  >  编程教程  >  动态规划  >  概率DP实例讲解

概率DP实例讲解

点击打开在线编译器,边学边练

在动态规划中,概率DP一般会用于研究有关于概率,步数,期望等问题。

简单总结为以下四个点:

(1)数学期望 P=Σ每一种状态*对应的概率。

(2)因为不可能枚举完所有的状态,有时也不可能枚举完,比如抛硬币,有可能一直是正面,etc。 但是现在发现大多数题就是手动找公式或者DP推出即可,只要处理好边界,然后写好方程,代码超级简短。与常规的求解不同,数学期望经常逆向推出。

(3)比如常规的dp[x]可能表示到了x这一状态有多少最后答案是dp[n]。而数学期望的dp[x]一般表示到了x这一状态还差多少,最后答案是dp[0]

(4)什么时候可以互相计算呢?关键在于所求期望的变量值是否会随着过程变化而变化!!!而不仅仅和所处位置有关!!!这种情况下,我们可以记录到当前状态所需的步数,最后就可以算期望。


例题一:涂格子

n个格子,每次随机涂一个,求涂m次后期望涂色格子数。

如概述所说,设计状态f[i]表示涂i次后的答案。转移时考虑这次是涂了的还是没涂的。

转移方程为转移方程

另外,可证明可证明


例题二:小孩和礼物

有n个礼物盒和m个小孩,每个盒子里有一个礼物。所有人轮流开盒子,每次打开一个随机盒子,如果里面有礼物就拿走(如果被开过了就没有礼物了)。问所有人拿走礼物的期望数量。

一个礼物=一个打开过的盒子。f[i]表示i个人拿走礼物的期望,相当于表示涂i次期望涂色格子数量。同涂格子2。


例题三:亚瑟王的生日庆典

亚瑟王过生,他每天抛一枚硬币,正面向上的概率是p。办庆典要花钱,在第i天要花(2i−1)千元。求正面向上数≥k次时的期望花钱数。

f[i]表示正面向上i次的期望花钱。转移时考虑是否掷到正面,容易列出转移f[i]=(1−p)f[i]+pf[i−1]+正面向上i次当天期望花费。

需要计算g[i]表示正面向上i次的期望天数,则当天期望开销=2×g[i]−1。g[i]=(1−p)g[i]+pg[i−1]+1。



知识点标签:动态规划


本文固定URL:https://www.dotcpp.com/course/996

上一课:

什么是概率DP?

下一课:

什么是线性DP?

算法竞赛教程
第一章 算法基础
第二章 搜索算法
第三章 排序算法
第四章 字符串相关
第五章 数学相关
第六章 动态规划
第七章 数据结构
第八章 图论
第九章 计算几何
第十章 其他算法
Dotcpp在线编译      (登录可减少运行等待时间)