試題 算法提高 概率計(jì)算（動(dòng)態(tài)規(guī)劃）

問(wèn)題描述
　　生成n個(gè)∈[a,b]的隨機(jī)整數(shù)，輸出它們的和為x的概率。
輸入格式
　　一行輸入四個(gè)整數(shù)依次為n，a，b，x，用空格分隔。
輸出格式
　　輸出一行包含一個(gè)小數(shù)位和為x的概率，小數(shù)點(diǎn)后保留四位小數(shù)
樣例輸入
2 1 3 4
樣例輸出
0.3333
思路：
此題是一種概率題，題目意思就是隨機(jī)出n個(gè)整數(shù)范圍是a-b然后讓我們求n個(gè)整數(shù)和為x的概率為多少？
我們這時(shí)知道a到b的數(shù)出現(xiàn)的概率，概率為：1/（a-b+1）這就是他們每個(gè)數(shù)出現(xiàn)的概率。
那要求n個(gè)隨機(jī)出來(lái)的數(shù)的x的概率，我們假設(shè)隨機(jī)2數(shù)時(shí)的和出現(xiàn)的概率，我們第一個(gè)數(shù)為n時(shí) 那么第二個(gè)數(shù)的概率就是x-n這個(gè)數(shù)可能出現(xiàn)的概率 在1/（a-b+1） 應(yīng)該上面是出現(xiàn)x-n的概率x想要2個(gè)出現(xiàn)的概率就是他們概率的乘積。
從上面得知我們可以用動(dòng)態(tài)規(guī)劃的方式了完成，我們建立dp[i][j]表示當(dāng)在a-b之間抽i個(gè)數(shù) 他們的和為j的概率為多少。
我們把dp[1][a-b] 的概率放入數(shù)組中 1/(b-a+1)概率。
我們?cè)诮?個(gè)for循環(huán)，第一層表示當(dāng)前抽幾個(gè)數(shù)，第二層表示當(dāng)前的第一個(gè)數(shù)為多少 ，第三層表示抽出來(lái)的數(shù)和。
我們知道 二個(gè)數(shù)的概率+=第一數(shù)的概率第二個(gè)數(shù)的概率 把出現(xiàn)這個(gè)概率相加就是總概率。
我們就真的轉(zhuǎn)移方程就是：dp[i][m]+=1/(b-a+1)*dp[i-1][m-j]

程序：

n,a,b,x=map(int,input().split())
dp=[[0 for i1 in range(x+2)] for i in range(n+5)]  #初始化
for i in range(a,b+1):  #把a(bǔ)-b的概率放在dp中
    dp[1][i]=1/(b-a+1)
for i in range(2,n+1):  #抽幾個(gè)數(shù)
    for j in range(a,b+1):  #第一個(gè)數(shù)為
        for m in range(j,x+1):  #抽出來(lái)的數(shù)可以組出的數(shù)
            dp[i][m]+=dp[i-1][m-j]/(b-a+1)

print("{:.4f}".format(dp[n][x]))

禁止轉(zhuǎn)載。僅用于自己學(xué)習(xí)。對(duì)程序錯(cuò)誤不負(fù)責(zé)。