试题 算法提高 概率计算（动态规划）
问题描述
生成n个∈[a,b]的随机整数，输出它们的和为x的概率。
输入格式
一行输入四个整数依次为n，a，b，x，用空格分隔。
输出格式
输出一行包含一个小数位和为x的概率，小数点后保留四位小数
样例输入
2 1 3 4
样例输出
0.3333
思路：
此题是一种概率题，题目意思就是随机出n个整数范围是a-b然后让我们求n个整数和为x的概率为多少？
我们这时知道a到b的数出现的概率，概率为：1/（a-b+1）这就是他们每个数出现的概率。
那要求n个随机出来的数的x的概率，我们假设随机2数时的和出现的概率，我们第一个数为n时 那么第二个数的概率就是x-n这个数可能出现的概率 在1/（a-b+1） 应该上面是出现x-n的概率x想要2个出现的概率就是他们概率的乘积。
从上面得知我们可以用动态规划的方式了完成，我们建立dp[i][j]表示当在a-b之间抽i个数 他们的和为j的概率为多少。
我们把dp[1][a-b] 的概率放入数组中 1/(b-a+1)概率。
我们在建立3个for循环，第一层表示当前抽几个数，第二层表示当前的第一个数为多少 ，第三层表示抽出来的数和。
我们知道 二个数的概率+=第一数的概率第二个数的概率 把出现这个概率相加就是总概率。
我们就真的转移方程就是：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的概率放在dp中
dp[1][i]=1/(b-a+1)
for i in range(2,n+1): #抽几个数
for j in range(a,b+1): #第一个数为
for m in range(j,x+1): #抽出来的数可以组出的数
dp[i][m]+=dp[i-1][m-j]/(b-a+1)
print("{:.4f}".format(dp[n][x]))
禁止转载。仅用于自己学习。对程序错误不负责。
