为什么这种在两个数组中选择索引的 DFS + Memoization 解决方案会导致 TLE，而类似的方法却不会？

Question

我正在解决一个问题，我需要通过在特定约束下从两个数组中选择索引来最大化分数：

问题陈述：

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 中那么有帮助有人可以详细解释一下吗？

谢谢！

Answer 1

解决方案1：

• 时间复杂度：O(m * n^2)

  • dfs(i, j)

    为

    j

    中的每个索引

    b

    探索

    i

    中的所有有效索引

    a

    。
  • 记忆中的总状态：O(m * n)。
  • 每个状态执行 O(n) 工作（循环遍历

    b

    中的索引）。
  • 总复杂度：O(m * n^2)。

解决方案2：

• 时间复杂度：O(m * n)

  • dfs(i, picked)

    每一步都会做出两个选择：选择或跳过。
  • 记忆中的总状态：O(m * n)。
  • 每个状态都执行 O(1) 工作（二元决策）。
  • 总复杂度：O(m * n)。

主要区别：

• 解决方案 1 对每个状态的

  b

  中的剩余索引进行循环。
• 解决方案 2 只对每个状态进行二元选择。

TLDR：两者都没有 O(n^2) 时间复杂度。

另外，我相信解决方案一也有 O(n^4) 的最坏情况（无法修剪无效路径）