機率與期望值動態規劃（probability and expectation DP）

有些過程牽涉機率：你擲骰子並走出那麼多格、你不停擲硬幣直到出現正面、一個隨機漫步者向左或向右走一步。像「我到達目標的機率是多少？」或「平均要幾步才完成？」這類問題，由表格存放機率或期望值（而非成本）的動態規劃來回答。結構是熟悉的——把問題拆成狀態與轉移——但合併運算是以機率加權的平均，其正當性來自全期望公式與期望值的線性性質。

核心工具是對第一個隨機步驟取條件。令 E[s] 為從狀態 s 出發某量的期望值。若從 s 過程以機率 p(s -> s') 移到狀態 s'，則 E[s] = （當下的貢獻）+ 在 s' 上對 p(s -> s') 乘以 E[s'] 求和。這就是全期望公式：整體期望是各條件期望的平均，並以每個分支的可能性加權。對機率而言形狀相同，只是去掉當下的貢獻：Prob[從 s 到達目標] = 在 s' 上對 p(s -> s') 乘以 Prob[從 s' 到達目標] 求和。一個乾淨的例子：擲公正硬幣到出現一次正面所需的期望次數。令 E 為該期望；以機率 1/2 你一擲就得正面（完成），以機率 1/2 你白擲一次又回到起點，所以 E = 1 + (1/2) E，得 E = 2。這種自我參照很典型，用代數求解即可。

當狀態圖是有向無環圖（沒有狀態能直接或間接回到自己）時，你只要按逆拓樸順序求值狀態，就和普通動態規劃一樣。真正的麻煩是有環：若狀態之間可以互相重訪（如硬幣例子或隨機漫步），方程式便互相遞迴，你無法只掃一遍就把表填好——你必須解一個線性方程組，小情形用代入、一般情形用高斯消去。常見的陷阱是：明明過程可能成環，卻當作它有乾淨的無環順序來處理；另一個是忘了期望值的線性性質讓你即使底層事件相依也能把期望貢獻相加，而這往往能大幅簡化狀態。