动态编程骰子总数方式

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作为不同的解决方案）。

总结上面的记忆（如果你不了解记忆，你可以学习一些关于动态规划的基本知识），我们来解决。