DynamicProgramming количество костей количество способов

Question

Приведенные n кубиков, каждый из которых имеет m лиц, пронумерованных от 1 до m, найти количество способов получить сумму X. X - это суммирование значений на каждой грани при броске всех кубиков. 4 + 3 и 3 + 4 следует рассматривать одинаково. Не считайте разные перестановки. Пример для п = 2, т = 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 в качестве разных решений).

Подведите итог выше с помощью запоминания (если вы не имеете представления о запоминании, вы можете узнать некоторые основные вещи о динамическом программировании), мы придем к решению.