为何DFS+记忆化选双数组索引的两种解法效率差异显著？

题目说明 #

给定大小为4的整数数组a和大小至少为4的整数数组b，需从b中选择4个满足i₀ < i₁ < i₂ < i₃的索引，计算得分a[0] * b[i₀] + a[1] * b[i₁] + a[2] * b[i₂] + a[3] * b[i₃]并返回最大得分。

示例输入：
a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]
输出：26

两种解法 #

Solution 1（超时TLE） #

class Solution:
    def maxScore(self, a, b):
        def dfs(i, j):
            if i == len(a):  # 处理完a中所有元素
                return 0
            if (i, j) in memo:  # 返回记忆化结果
                return memo[(i, j)]

            max_result = float("-inf")
            for index in range(j, len(b)):
                if len(b) - index < len(a) - i:  # b中剩余元素不足，无法完成选择
                    break
                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)

Solution 2（高效通过） #

class Solution:
    def maxScore(self, a, b):
        def dfs(i, picked):
            if picked == 4:  # 选完4个元素（对应a的所有元素）
                return 0
            if len(b) - i + picked < 4:  # 剩余元素+已选数量不足4，无法完成选择
                return float("-inf")
            if (i, picked) in memo:  # 返回记忆化结果
                return memo[(i, picked)]

            pick = a[picked] * b[i] + dfs(i + 1, picked + 1)  # 选择当前b[i]，匹配a[picked]
            skip = dfs(i + 1, picked)  # 跳过当前b[i]

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

        memo = {}
        return dfs(0, 0)

效率差异核心原因解析 #

两种解法的效率差距本质是时间复杂度的量级差异，核心区别在于状态定义和递归分支的处理方式：

1. 状态总数与单状态处理开销 #

• Solution 1：状态是(i, j)，其中i是a的当前索引（仅0-3四种可能），j是b中当前可选的起始索引（0到n-1，n为b的长度），总状态数为4*n。但每个状态的计算需要遍历从j到n-(4-i)的所有index，这一步是O(n)级别的循环操作，因此总时间复杂度为O(n²)。当b的长度很大时（比如n=1e4），总操作量会达到4e8次，远超LeetCode的时间限制。
• Solution 2：状态是(i, picked)，其中i是b的当前索引（0到n-1），picked是已选元素的数量（仅0-4五种可能），总状态数为5*n。每个状态仅处理两个分支（选或不选当前b[i]），单状态处理是O(1)的常数操作，总时间复杂度为O(n)，即使n很大也能高效运行。

2. 递归分支的冗余度 #

• Solution 1的递归逻辑是“在b中从j开始逐个尝试选元素匹配a[i]”，每一步都会产生多个递归分支，即使有记忆化，第一次计算(i,j)时的循环遍历仍会带来大量额外开销，且这些循环无法通过记忆化直接规避。
• Solution 2的递归逻辑是“对当前b[i]做二选一决策”，每一步仅产生两个分支，所有状态都是线性遍历b的元素，记忆化可以完全覆盖所有可能的状态，没有冗余的循环操作。

3. 剪枝的实际效果 #

• Solution 1的剪枝是“剩余元素不足时break循环”，但仍需遍历到触发条件的位置才能停止，当n很大时，前面的循环次数依然很多。
• Solution 2的剪枝是“递归入口直接判断剩余元素是否足够”，提前终止无效的递归分支，且因为每个状态只处理一次，剪枝的额外开销可以忽略不计。

内容的提问来源于stack exchange，提问作者souparno majumder