什么是概率DP？

92895 閱讀 0 評論 0 點贊

一、概率DP

顧名思義，概率DP就是動態(tài)規(guī)劃求概率的問題。一般來說，我們將dp數(shù)組存放的數(shù)據(jù)定義為到達此狀態(tài)的概率，那么我們初值設置就是所有初始狀態(tài)概率為1，最終答案就是終末狀態(tài)dp值了。

我們在進行狀態(tài)轉移時，是從初始狀態(tài)向終末狀態(tài)順推，轉移方程中大致思路是按照當前狀態(tài)去往不同狀態(tài)的位置概率轉移更新DP，且大部分是加法。

二、期望DP

用于求解期望的DP。這類問題一般將dp數(shù)組存放的數(shù)據(jù)定義為到達終態(tài)還需要的期望值。那么初值設置就是終末狀態(tài)期望為0，答案就是初始狀態(tài)的dp值了。

我們在進行狀態(tài)轉移時，一般是從終末狀態(tài)逆推到起始狀態(tài)，轉移方程大致思路是找到當前狀態(tài)所有可以轉移到的狀態(tài)，將它們的期望依概率相加即可。這是對于不同行動有概率的情況，比如投骰子。但對于多種情況互斥可選的時候(一般題目會告知你取最優(yōu)策略)，比如飛行棋投骰子/鉆隧道二選一移動，這時可能就需要取max或min來轉移了。

三、總結的規(guī)律：

1. 期望可以分解成多個子期望的加權和，權為子期望發(fā)生的概率，即 E(aA+bB+…) = aE(A) + bE(B) +…+1；

2. 期望從后往前找，一般dp[n]=0，dp[0]是答案；

3. 解決過程，找出各種情況乘上這種情況發(fā)生的概率，求和。

點贊(0)