n 類 Bug,s 個子系統。每天隨機發現一個 Bug,類別與子系統均勻獨立分布。求期望天數,使得「每類 Bug 至少出現一次」且「每子系統至少出現一次」。
dp[i][j]:已發現 i 類 Bug、j 個子系統有 Bug 時,達到目標 (n, s) 所需的期望剩餘天數。
邊界:dp[n][s] = 0。
當前狀態 (i, j),下一天四種情況:
| 情況 | 概率 | 新狀態 |
|---|---|---|
| 舊類、舊系統 | i/n * j/s | (i, j) |
| 新類、舊系統 | (n-i)/n * j/s | (i+1, j) |
| 舊類、新系統 | i/n * (s-j)/s | (i, j+1) |
| 新類、新系統 | (n-i)/n * (s-j)/s | (i+1, j+1) |
期望方程:
dp[i][j] = 1 + p00*dp[i][j] + p10*dp[i+1][j] + p01*dp[i][j+1] + p11*dp[i+1][j+1]
移項得:
dp[i][j] = (1 + p10*dp[i+1][j] + p01*dp[i][j+1] + p11*dp[i+1][j+1]) / (1 - p00)
i 從 n 遞減到 0,j 從 s 遞減到 0(依賴右/下狀態)。