動態編程骰子總數方式

Question

給定n個骰子，每個骰子都有m個面，編號從1到m，找出求和總和X的方法數.X是所有骰子拋出時每個面上值的總和。 4 + 3和3 + 4應該相同。 不考慮不同的排列。 實施例對於n = 2，M = 6，且X = 7 否的方式應該是3（1,6和2,5和3,4）

Answer 1

我寫一個短Python代碼爲您：

d = {} 


def f(n, m, x): 
    if n == 0 and x == 0: 
     return 1 
    if n < 0 or m == 0 or x < 0: 
     return 0 
    if d.get((n, m, x)) is not None: 
     return d[(n, m, x)] 
    ret = f(n - 1, m, x - m) + f(n, m - 1, x) 
    d[(n, m, x)] = ret 
    return ret 


print f(2, 6, 7) #return 3, as your example 
print f(3, 6, 7) #return 4, (2 2 3), (1 3 3), (1 2 4), (1 1 5) 

一個簡單的解釋：

f(n, m, x) = the ways of now we have n dices, and now the dice numbered from 1 to m to achieve sum x. 

而且

f(n, m, x) = f(n - 1, m, x - m) + f(n, m - 1, x) 

然後

f(n - 1, m, x - m): throw a dice and it must be number m. 
f(n, m - 1, x): don't throw a dice, and we let the dice number decrease 1(so we can't throw a dice with number m now, it could be m-1 as most) 

爲什麼我們必須擲出一個數字m的骰子？哦，那樣，我們可以得到一個不同於其他解決方案的解決方案（我的意思是避免計數3+4和4+3作爲不同的解決方案）。

總結上面的記憶（如果你不瞭解記憶，你可以學習一些關於動態規劃的基本知識），我們來解決。