python-概率计算

解题思路:

动态规划

建立数组dp = [max(n,a,b,x)+1][(n+1)]     注意这里不要直接写成dp = [x+1][n+1]，因为在后面的计算中数组可能会越界，没修改前题测为91分

其中dp[i][j] 表示第i个数的和为j的概率,状态转移方程dp[i][j] = dp[i][j] + dp[i-1][j-k]*dp[1][k]

注意事项:

参考代码:

def f(n,a,b,x):  
    dp = [[0 for j in range(max(n,a,b,x)+1)] for i in range(n+1)]  
    for i in range(a,b+1):      #初始化dp数组
        dp[1][i] = 1/(b-a+1)  
  
    for i in range(2,n+1):      #把[i = 2 to n]个数的情况扫一遍
        for j in range(a*i,x+1):  #把可能得到的和扫一遍，当有i个数时的和最小为a*i
            for k in range(a,b+1): #把中间数k扫一遍k的范围为[a,b] 
                if j - k > 0:  
                    dp[i][j] = dp[i][j] + dp[i-1][j-k]*dp[1][k]  
                else:  
                    break  
    print('%.4f' % dp[n][x])  
     
if __name__ == '__main__':    
    n,a,b,x= map(int,input().strip().split())    
    f(n,a,b,x)