本文共 1982 字，大约阅读时间需要 6 分钟。
第一种思路是，每个骰子的点数从最小到最大，假设为1-6，那么所有的骰子从最小1开始，我们假设一种从左向右的排列，右边的最低，索引从最低开始，判断和的情况。
def setTo1(dices, start, end): for i in range(start, end): dices[i] = 1def probability(n, s, dmax = 6, dmin = 1): if s < n * dmin or s > n * dmax : return 0 dices = [1] * n i = n - 1 total = 0 while i >= 0: curSum = sum(dices) if curSum == s: print dices total += 1 # find first one that can +1 for j in range(i, -1, -1): if dices[j] < dmax and s - sum(dices[0:j+1]) >= n - j*dmin: dices[j] += 1 setTo1(dices, j + 1, n) i = n - 1 break else: i -= 1 elif curSum < s: if dices[i] < dmax: dices[i] += 1 i = n - 1 else: i -= 1 print "total = {0}, prob = {1}%".format(total, total*100/dmax**n) return total 若当前和小于s，则检验当前索引处的骰子能否增加1，若能，则增加，否则查看其前面的能否增加。若相等，那么我们统计信息后，要变化当前的情形，以便处理下一种情况，因为 索引是从低位开始到当前位的，所以我们从当前索引开始，向前找能继续增加的骰子，这里的判断标准是当前骰子的点数小于最小值，而且要保证其后的骰子的最小值为1，比如 1,4,1, s = 6， 当前索引指向4， 这里的4虽然小于最大点数6， 但若其再加一，第三个骰子就的为0，这不符合要求。若找到可以加一的骰子，那就将该骰子点数加1， 将其后的骰子都置为1，索引回到最后，开始重新加起。如：1,1,6，s = 8， 索引指向6， 修改后为1,2,1，索引指向最后的1,。若没有找到可以再增加的骰子，那么就结束。如6,1,1，s = 8。 其实若给定的n不大的话，我们可以设一个n位整数，从n个1开始，逐次加一，来判断各个位的和是否满足要求，直到达到最大值，n个6。
这个问题其实动态规划的特点很明显。
''' @ state function: dp[i, j]: the total cases of sum = j, composed by i dices @ state tranfor function: dp[i, j] = sum(dp[i - 1, j - k]) for k in [dmin, dmax] @ dp[i, j] = 0, j > i * dmax or j < i * dmin @ init condition: dp[1, k] = 1, for k in [dmin, dmax], dp[1, k] = 0, for other k''' def dp_probability(n, s, dmax = 6, dmin = 1): if s < n * dmin or s > n * dmax : return 0 dp1 = [0] * (n * dmax + 1) #init dp[1, :] for i in range(1, dmax + 1): dp1[i] = 1 # i: the number of dices for i in range(2, n + 1): dp2 = [0] * (n * dmax + 1) # j: range of i dices for j in range(dmin * i, dmax * i + 1): # k: range of new added dice for k in range(dmin, dmax + 1): if j > k : dp2[j] += dp1[j - k] print dp2 dp1 = dp2 print "total = {0}, prob = {1}%".format(dp2[s], dp2[s]*100/dmax**n) return dp2[s] 转载地址：http://dumji.baihongyu.com/