Почему это решение работает в Javascript, но не работает в Python? (Динамическое программирование)

Благодаря статье, которой поделился @Jared Smith, я смог это понять.

Проблема вызвана тем, как python обрабатывает аргументы по умолчанию. Из статьи:

В Python при передаче изменяемого значения в качестве аргумента по умолчанию в функцию аргумент по умолчанию изменяется каждый раз, когда изменяется это значение.

Мой memo словарь менялся при каждом звонке. Поэтому я просто изменил memo=None и добавил проверку, был ли это первый вызов функции:

def canSum(targetSum, numbers, memo=None):
    if memo == None:
        memo = {}

    if targetSum in memo:
        return memo[targetSum]
    if targetSum == 0:
        return True
    if targetSum < 0:
        return False

    for n in numbers:
        remainder = targetSum - n
        if canSum(remainder, numbers, memo):
            memo[targetSum] = True
            return True

    memo[targetSum] = False
    return False


print(canSum(7, [2, 3])) # True
print(canSum(7, [5, 3, 4, 7])) # True
print(canSum(7, [2, 4])) # False
print(canSum(8, [2, 3, 5])) # True
print(canSum(3000, [7, 14])) # False -> Works fast with large inputs!

В вашем механизме сохранения есть ошибка.

Когда вы вызываете функцию в первый раз:

print(canSum(7, [2, 3]))

Этот вызов вернет true и создаст ключ в словаре со значением true( 7 : true).
Это причина, почему это не работает

Теперь проверим третий вызов:

print(canSum(7, [2, 4]))

Первое, что делает ваша функция, это проверяет, есть ли число 7 в словаре:

if targetSum in memo:
    return memo[targetSum]

И поскольку с 1-го вызова у вас уже есть номер 7 в словаре, он будет искать его и возвращать его значение - и с 1-го вызова значение для номера 7 равно True

Это словарь до и после первого вызова.

{}                                    # before first call
{1: False, 3: True, 5: True, 7: True} # after first call

После первого вызова этот словарь будет возвращать True каждый раз, когда вы вызываете функцию с номером 7.
И поскольку Python использует общий аргумент по умолчанию (это объясняется в комментарии Джареда Смита), каждый вызов будет возвращать True для числа 7.

Как это исправить? Вы должны сохранить как targetSum, так и nums в словаре и проверить оба значения.

Есть два способа сделать это:

1-й способ: Инкапсулируйте targetSum и nums в кортеж и используйте этот кортеж в качестве ключа. Вот как будет выглядеть этот дикт

{
  (7, (2, 3)) : True,
  (7, (5, 3, 4, 7)) : True,
  (7, (2, 4)) : False
}

Это реализация этого:

keyTuple = (targetSum, tuple(numbers))
if keyTuple in memo:
    return memo[keyTuple]

if targetSum == 0:
    return True
if targetSum < 0:
    return False

for n in numbers:
    remainder = targetSum - n
    if canSum(remainder, numbers, memo):
        memo[keyTuple] = True
        return True

memo[keyTuple] = False
return False

Вы также должны преобразовать list в tuple , потому что python не позволяет использовать списки в качестве ключей для словарей.

Второй способ - использовать словарь словарей. Что-то вроде этого.

{
 7: {
   (2,3): True,
   (5, 3, 4, 7): True
   (2,4): False
 }

}

Это реализация:

def canSum(targetSum, numbers, memo = {}):
numbersTuple = tuple(numbers)

if targetSum in memo:
    targetDict = memo[targetSum]
    if numbersTuple in targetDict:
        return targetDict[numbersTuple]
else:
    memo[targetSum] = {}

if targetSum == 0:
    return True
if targetSum < 0:
    return False

for n in numbers:
    remainder = targetSum - n
    if canSum(remainder, numbers, memo):
        targetDict = memo[targetSum]
        targetDict[numbersTuple] = True
        return True

targetDict = memo[targetSum]
targetDict[numbersTuple] = False
return False

Если вы чего-то не понимаете, напишите мне комментарий :)