逆著遞推求解
題意：
一個軟件有s個子系統，會產生n種bug
某人一天發現一個bug,這個bug屬于一個子系統，屬于一個分類
每個bug屬于某個子系統的概率是1/s,屬于某種分類的概率是1/n
問發現n種bug,每個子系統都發現bug的天數的期望。

求解：
dp[i][j]表示已經找到i種bug,j個系統的bug后要達到目標狀態的天數的期望
dp[n][s]=0;要求的答案是dp[0][0];
dp[i][j]可以轉化成以下四種狀態:
dp[i][j],發現一個bug屬于已經有的i個分類和j個系統。概率為(i/n)*(j/s);
dp[i][j+1],發現一個bug屬于已有的分類，不屬于已有的系統.概率為 (i/n)*(1-j/s);
dp[i+1][j],發現一個bug屬于已有的系統，不屬于已有的分類,概率為 (1-i/n)*(j/s);
dp[i+1][j+1],發現一個bug不屬于已有的系統，不屬于已有的分類,概率為 (1-i/n)*(1-j/s);
整理便得到轉移方程
dp[i][j]=p1*dp[i+1][j+1]+p2*dp[i+1][j]+p3*dp[i][j+1]+p4*dp[i][j]+1; //dp[i][j]表示的就是到達狀態i,j的期望，+1是因為一天后

=>dp[i][j]=(p1*dp[i+1][j+1]+p2*dp[i+1][j]+p3*dp[i][j+1]+1)/(1-p4);?

?

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cstdlib> 6 #include <cmath> 7 #include <set> 8 #include <map> 9 #include <queue> 10 #include <vector> 11 #define INF 0x3f3f3f3f 12 using namespace std; 13 14 double dp[1010][1010]; 15 int main() 16 { 17 int n, s; 18 scanf("%d %d", &n, &s); 19 for(int i = n; i >= 0; i--) 20 { 21 for(int j = s; j >= 0; j--) 22 { 23 if(i == n && j == s) 24 continue; 25 dp[i][j] = ((n-i)*j*dp[i+1][j]+i*(s-j)*dp[i][j+1]+(n-i)*(s-j)*dp[i+1][j+1]+n*s)*1.0/(n*s-i*j); 26 } 27 } 28 printf("%.4f\n", dp[0][0]); 29 return 0; 30 }

?

轉載于:https://www.cnblogs.com/luomi/p/5693049.html

總結

以上是生活随笔為你收集整理的poj2096_概率dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。