在動態(tài)規(guī)劃中，概率DP一般會用于研究有關(guān)于概率，步數(shù)，期望等問題。

簡單總結(jié)為以下四個點：

（1）數(shù)學期望 P=Σ每一種狀態(tài)*對應的概率。

（2）因為不可能枚舉完所有的狀態(tài)，有時也不可能枚舉完，比如拋硬幣，有可能一直是正面，etc。 但是現(xiàn)在發(fā)現(xiàn)大多數(shù)題就是手動找公式或者DP推出即可，只要處理好邊界，然后寫好方程，代碼超級簡短。與常規(guī)的求解不同，數(shù)學期望經(jīng)常逆向推出。

（3）比如常規(guī)的dp[x]可能表示到了x這一狀態(tài)有多少，最后答案是dp[n]。而數(shù)學期望的dp[x]一般表示到了x這一狀態(tài)還差多少，最后答案是dp[0]。

（4）什么時候可以互相計算呢？關(guān)鍵在于所求期望的變量值是否會隨著過程變化而變化！??！而不僅僅和所處位置有關(guān)?。?！這種情況下，我們可以記錄到當前狀態(tài)所需的步數(shù)，最后就可以算期望。

例題一：涂格子

n個格子，每次隨機涂一個，求涂m次后期望涂色格子數(shù)。

如概述所說，設計狀態(tài)f[i]表示涂i次后的答案。轉(zhuǎn)移時考慮這次是涂了的還是沒涂的。

轉(zhuǎn)移方程為

另外，可證明

例題二：小孩和禮物

有n個禮物盒和m個小孩，每個盒子里有一個禮物。所有人輪流開盒子，每次打開一個隨機盒子，如果里面有禮物就拿走（如果被開過了就沒有禮物了）。問所有人拿走禮物的期望數(shù)量。

一個禮物=一個打開過的盒子。f[i]表示i個人拿走禮物的期望，相當于表示涂i次期望涂色格子數(shù)量。同涂格子2。

例題三：亞瑟王的生日慶典

亞瑟王過生，他每天拋一枚硬幣，正面向上的概率是p。辦慶典要花錢，在第i天要花(2i?1)千元。求正面向上數(shù)≥k次時的期望花錢數(shù)。

f[i]表示正面向上i次的期望花錢。轉(zhuǎn)移時考慮是否擲到正面，容易列出轉(zhuǎn)移f[i]=(1?p)f[i]+pf[i?1]+正面向上i次當天期望花費。

需要計算g[i]表示正面向上i次的期望天數(shù)，則當天期望開銷=2×g[i]?1。g[i]=(1?p)g[i]+pg[i?1]+1。