Почему это решение DFS + Memoization для выбора индексов в двух массивах приводит к TLE, а аналогичный подход — нет? ⇐ Python

[Anonymous]

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

Код: Выделить всё

You are given an integer array a of size 4 and another integer array b of size at least 4.

You need to choose 4 indices i0, i1, i2, and i3 from the array b
such that i0 < i1 < i2 < i3. Your score will be equal to the
value a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3].

Return the maximum score you can achieve.

Example:
Input: a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]
Output: 26
Explanation: Choose indices 0, 1, 2, and 5 from b.

Моя попытка:
Я написал два решения на основе рекурсии и запоминания, но одно из них приводит к TLE для большего n. Вот два подхода:
Решение 1 (TLE)

Код: Выделить всё

class Solution:
def maxScore(self, a, b):
def dfs(i, j):
if i == len(a):  # All elements in `a` processed
return 0
if (i, j) in memo:  # Return memoized result
return memo[(i, j)]

max_result = float("-inf")
for index in range(j, len(b)):
if len(b) - index < len(a) - i:  # Not enough elements left in `b`
continue
max_result = max(max_result, a[i] * b[index] + dfs(i + 1, index + 1))

memo[(i, j)] = max_result
return max_result

memo = {}
return dfs(0, 0)

Решение 2 (работает)

Код: Выделить всё

class Solution:
def maxScore(self, a, b):
def dfs(i, picked):
if picked == 4:  # All elements in `a` processed
return 0
if len(b) - i + picked < 4:  # Not enough elements left in `b`
return float("-inf")
if (i, picked) in memo:  # Return memoized result
return memo[(i, picked)]

pick = a[picked] * b[i] + dfs(i + 1, picked + 1)  # Pick this index
skip = dfs(i + 1, picked)  # Skip this index

memo[(i, picked)] = max(pick, skip)
return memo[(i, picked)]

memo = {}
return dfs(0, 0)

Вопрос:
Почему Решение 1 приводит к TLE, а Решение 2 работает эффективно?
Я думаю, что без запоминания оба решения будут иметь одинаковую временную сложность O (2^n) выбора или не выбора, но я не могу точно определить, почему сокращение или мемоизация, похоже, не помогают так сильно, как в решении 2. Может ли кто-нибудь дать подробное объяснение?
Спасибо!

Подробнее здесь: https://stackoverflow.com/questions/792 ... arrays-lea