Количество способов сложить сумму S с N числами

Question

Скажем, S = 5 и N = 3, решения будут выглядеть так: <0,0,5> <0,1,4> <0,2,3> <0,3,2> <5,0, 0> <2,3,0> <3,2,0> <1,2,2> и т. Д.

В общем случае для решения проблемы можно использовать N вложенных циклов. Запустите N вложенного цикла, внутри них проверьте, не добавляются ли переменные цикла в S.

Если мы не знаем N заранее, мы можем использовать рекурсивное решение. На каждом уровне запускайте цикл, начинающийся с 0 до N, а затем снова вызывайте саму функцию. Когда мы достигнем глубины N, посмотрим, получаются ли полученные числа до S.

Любое другое решение для динамического программирования?

Answer 1

Попробуйте эту рекурсивную функцию:

f(s, n) = 1                                    if s = 0
        = 0                                    if s != 0 and n = 0
        = sum f(s - i, n - 1) over i in [0, s] otherwise

Чтобы использовать динамическое программирование, вы можете кэшировать значение f после его оценки и проверить, существует ли уже значение в кэше, прежде чем оценивать его.

Answer 2

Есть формула замкнутой формы: бином (s + n - 1, n)

Эти числа являются симплексными числами .

Если вы хотите их вычислить, используйте функцию log gamma или арифметику произвольной точности.

См. https://math.stackexchange.com/questions/2455/geometric-proof-of-the-formula-for-simplex-numbers

Answer 3

У меня есть своя формула для этого.Мы вместе с моим другом Джио сделали следственный отчет по этому поводу.Полученная нами формула: [2 raised to (n-1) - 1], где n - это число, которое мы ищем, сколько у него добавлений.

Давайте попробуем.

• Если n равно 1: его добавления равны o.Там нет двух или более чисел, которые мы можем добавить, чтобы получить сумму 1 (исключая 0).Давайте попробуем большее число.
• Давайте попробуем 4. 4 has addends: 1+1+1+1, 1+2+1, 1+1+2, 2+1+1, 1+3, 2+2, 3+1.Итого 7. Давайте проверим по формуле.2 повышен до (4-1) - 1 = 2 повышен до (3) - 1 = 8-1 = 7.
• Давайте попробуем 15. 2 повышен до (15-1) - 1 =2 повышено до (14) - 1 = 16384 - 1 = 16383. Таким образом, существует 16383 способа добавления чисел, которые будут равны 15.

(Примечание: добавления являются только положительными числами.)

(Вы можете попробовать другие числа, чтобы проверить, верна ли наша формула.)

Answer 4

Это можно рассчитать в O(s+n) (или O(1), если вы не возражаете против приближения ) следующим образом:

Представьте, что у нас есть строка с n-1 X и s o. Так что для вашего примера s = 5, n = 3, одна строка примера будет

oXooXoo

Обратите внимание, что X делят буквы o на три различные группы: одна длиной 1, длиной 2 и длиной 2. Это соответствует вашему решению <1,2,2>. Каждая возможная строка дает нам другое решение, подсчитывая число o в строке (возможен 0: например, XoooooX будет соответствовать <0,5,0>) . Итак, подсчитав количество возможных строк этой формы, мы получим ответ на ваш вопрос.

Есть s+(n-1) позиций для выбора s o, поэтому ответ Choose(s+n-1, s).

Answer 5

Существует фиксированная формула для поиска ответа.Если вы хотите найти количество способов получить N в виде суммы R элементов.Ответ всегда: (N + R-1)! / ((R-1)! * (N)!) Или другими словами: (N + R-1) C (R-1)

Answer 6

Это на самом деле очень похоже на проблему Towers of Hanoi, без ограничения стекирования дисков только на больших дисках. У вас есть S дисков, которые могут быть в любой комбинации на N башнях. Так вот что заставило меня задуматься об этом.

Я подозреваю, что есть формула, которую мы можем вывести, которая не требует рекурсивного программирования. Мне нужно еще немного времени.