Ошибка типа: объект 'NoneType' не может быть повторен в рекурсии Python

#python #recursion #dynamic-programming

Вопрос:

В вопросе говорится:

Вам дается целочисленный массив монет, представляющих монеты разных номиналов, и gt;целочисленная сумма, представляющая общую сумму денег. Верните наименьшее количество монет, которое вам нужно, чтобы восполнить эту сумму. Если эта сумма денег не может быть составлена какой-либо комбинацией монет, верните -1.’

Вот что я пытаюсь сделать:

 def coinChange(coins, amount, final_list=[]):  """  :type coins: List[int]  :type amount: int  :rtype: int  """   if all(coins) gt; amount:  return -1  while amount gt; 0:  if amount - max(coins) gt;= 0:  amount -= max(coins)  final_list.append(max(coins))  else:  return coinChange(coins.remove(max(coins)), amount, final_list)   return len(final_list) coins = [1,2,5] amount = 11 coinChange(coins, amount)

Кто-нибудь может помочь, пожалуйста

1. if all(coins) gt; amount это неверно. all() возвращает True или False , нет смысла сравнивать это с amount .

2. Вы не должны использовать изменяемые типы в качестве аргументов по умолчанию. final_list=[] не будет делать то, что вы хотите; делайте что-то подобное final_list = None и в теле делайте if final_list is None: final_list = []

3. Пожалуйста, опубликуйте полную обратную связь, чтобы мы могли легко увидеть ошибку. И имейте в виду, что def coinChange(coins, amount, final_list=[]): по умолчанию создается пустой список final_list , и этот список всегда используется по умолчанию. Все вызовы для coinChange использования по умолчанию будут добавлены в этот список.

4. coins.remove(max(coins)) изменяет coins список на месте и возвращает None . Вот в чем причина ошибки.

5. Не стесняйтесь добавлять инструкции печати, отображающие значения, которые вы рассчитали по ходу работы. Это хороший способ следить за ходом выполнения. Кроме того, во многих IDE есть отладчики, они отлично подходят для этого. Или идите в старую школу и используйте pdb линейный отладчик python.

Ответ №1:

Есть ряд проблем, упомянутых в комментариях, я не собираюсь пытаться исправить остальные из них.

Причина конкретной ошибки, которую вы получаете, заключается в том, что remove() при изменении списка на месте он не возвращает измененный список. Таким образом, вы передаете None в качестве coins аргумента, когда выполняете рекурсивный вызов.

Поэтому вызовите remove() отдельно от вызова функции.

 else:  coins.remove(max(coins))  return coinChange(coins, amount, final_list)