Как применить рекурсию к этому коду о количестве способов суммирования до «N»?

Учитывая список целых чисел и целевое целое число N, я хочу найти количество способов, которыми можно сложить целые числа в списке, чтобы получить N. Повторение разрешено. Это код:

def countWays(arr, m, N): 

    count = [0 for i in range(N + 1)] 

    # base case 
    count[0] = 1

    # Count ways for all values up  
    # to 'N' and store the result 
    # m=len(arr)
    for i in range(1, N + 1): 
        for j in range(m): 

            # if i >= arr[j] then 
            # accumulate count for value 'i' as 
            # ways to form value 'i-arr[j]' 
            if (i >= arr[j]): 
                count[i] += count[i - arr[j]] 

    # required number of ways  
    return count[N]

(от Geeksforgeeks)

Любая идея о том, как это сделать с помощью рекурсии и запоминания?

Предназначена ли функция для печати количества упорядоченных последовательностей элементов из arr (имеющих mэлементов), допускающих повторения, сумма которых равна N?

— Eric Postpischil 10.04.2019 23:56

Добавлено объяснение

— smartprogrammer 11.04.2019 01:00

Если вы скопировали его из решения, он уже должен быть O(mN)

— Edeki Okoh 11.04.2019 01:06
python python-3.x math
10.04.2019 23:20
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
0
3
768
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Проблема, которую вы пытаетесь решить, такая же, как количество способов внести сдачу на сумму, заданную списком номиналов. В вашем случае сумма аналогична целевому номеру N, а номиналы аналогичны списку целых чисел. Вот рекурсивный код. Ссылка https://www.geeksforgeeks.org/coin-change-dp-7/

# Returns the count of ways we can sum 
# arr[0...m-1] coins to get sum N 
def count(arr, m, N ): 

    # If N is 0 then there is 1 
    # solution (do not include any coin) 
    if (N == 0): 
        return 1

    # If N is less than 0 then no 
    # solution exists 
    if (N < 0): 
        return 0; 

    # If there are no coins and N 
    # is greater than 0, then no 
    # solution exist 
    if (m <=0 and N >= 1): 
        return 0

    # count is sum of solutions (i) 
    # including arr[m-1] (ii) excluding arr[m-1] 
    return count( arr, m - 1, N ) + count( arr, m, N-arr[m-1] );
11.04.2019 01:24

Другие вопросы по теме

Как сохранить форму вывода кортежей для цикла в DataFrame Python
Проверка ввода и как ее улучшить
Как читать текстовый файл построчно, как набор команд
Передать переменную в read_csv в качестве аргумента?
Ошибка "InvalidHeaderValue" REST API "PUT Range" файловой службы Azure
Как установить разные атрибуты для ряда объектов Python
Как использовать Python csv для записи нескольких строк таблицы BeautifulSoup только для двух определенных столбцов?
Извлечь информацию внутри тега span
Как найти все индексы в двумерной матрице, где фрейм данных pandas имеет значения, отличные от NA
Plotly / Dash — Python, как остановить выполнение по истечении времени?

Похожие вопросы

Выбор Pandas Dataframe, удовлетворяющий членству
Как фильтровать элементы из последующих преобразований в конвейере, не отправляя «NoneType»?
Почему torch.nn.Sigmoid — это класс, а не метод?
Передать переменную в read_csv в качестве аргумента?
Python Beautifulsoup получает гиперссылку
Добавить разделитель в меню параметров в python с помощью Tkinter
Как установить разные атрибуты для ряда объектов Python
Извлечь информацию внутри тега span
Дополнительные вычисления после создания сводной таблицы для выбранных столбцов
Plotly / Dash — Python, как остановить выполнение по истечении времени?