Leetcode动态规划问题：缓存命中差异过大的性能瓶颈分析

我在解决LeetCode标记为Hard的动态规划问题《Profitable Schemes》时，自己的解法比讨论区找到的解法慢16倍。此前我熟悉“物品索引+1，选择保留/跳过当前物品”的递推逻辑（也就是高效解法的思路），但想练习“循环遍历物品”的技巧，以为两种方式效率相近，结果实际缓存命中数相差35倍：高效解法缓存命中692860次，我的解法命中24868771次，想弄清原因。

高效解法代码（耗时约0.5秒） #

from typing import List
from functools import cache

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:

        @cache
        def dfs(i, members, cur_profit):

            if i >= len(profit):
                if cur_profit >= minProfit and members <= n:
                    return 1
                else:
                    return 0

            ans = 0
            ans += dfs(i + 1, members, cur_profit)

            if members + group[i] <= n:
                ans += dfs(i + 1, members + group[i], min(cur_profit + profit[i], minProfit))

            return ans

        answer = dfs(0, 0, 0) % (10 ** 9 + 7)
        print(dfs.cache_info())

        return answer

solution = Solution()
answer = solution.profitableSchemes(
    100, 100,
    [2,5,36,2,5,5,14,1,12,1,14,15,1,1,27,13,6,59,6,1,7,1,2,7,6,1,6,1,3,1,2,11,3,39,21,20,1,27,26,22,11,17,3,2,4,5,6,18,4,14,1,1,1,3,12,9,7,3,16,5,1,19,4,8,6,3,2,7,3,5,12,6,15,2,11,12,12,21,5,1,13,2,29,38,10,17,1,14,1,62,7,1,14,6,4,16,6,4,32,48],
    [21,4,9,12,5,8,8,5,14,18,43,24,3,0,20,9,0,24,4,0,0,7,3,13,6,5,19,6,3,14,9,5,5,6,4,7,20,2,13,0,1,19,4,0,11,9,6,15,15,7,1,25,17,4,4,3,43,46,82,15,12,4,1,8,24,3,15,3,6,3,0,8,10,8,10,1,21,13,10,28,11,27,17,1,13,10,11,4,36,26,4,2,2,2,10,0,11,5,22,6]
)

我的低效解法代码（耗时约8.5秒） #

from typing import List
from functools import cache


class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        self.modulus = 10 ** 9 + 7
        self.groups = group
        self.profit = profit
        self.min_profit = minProfit
        self.n = n
        answer = self.solve(-1, n, 0) % self.modulus
        if minProfit == 0:
            answer += 1
        return answer

    @cache
    def solve(self, previous_crime_index, remaining_members, accumulated_profit):
        if remaining_members <= 0 or previous_crime_index == self.n - 1:
            return 0
        answer = 0
        for crime_index in range(previous_crime_index+1, len(self.groups)):
            capped_profit = min(accumulated_profit + self.profit[crime_index], self.min_profit)
            answer += self.solve(
                crime_index, remaining_members - self.groups[crime_index],
                capped_profit
            )
            answer = answer % self.modulus
            if self.profit[crime_index] + accumulated_profit >= self.min_profit and remaining_members - self.groups[crime_index] >= 0:
                answer += 1
        return answer % self.modulus

solution = Solution()
answer = solution.profitableSchemes(
    100, 100,
    [2,5,36,2,5,5,14,1,12,1,14,15,1,1,27,13,6,59,6,1,7,1,2,7,6,1,6,1,3,1,2,11,3,39,21,20,1,27,26,22,11,17,3,2,4,5,6,18,4,14,1,1,1,3,12,9,7,3,16,5,1,19,4,8,6,3,2,7,3,5,12,6,15,2,11,12,12,21,5,1,13,2,29,38,10,17,1,14,1,62,7,1,14,6,4,16,6,4,32,48],
    [21,4,9,12,5,8,8,5,14,18,43,24,3,0,20,9,0,24,4,0,0,7,3,13,6,5,19,6,3,14,9,5,5,6,4,7,20,2,13,0,1,19,4,0,11,9,6,15,15,7,1,25,17,4,4,3,43,46,82,15,12,4,1,8,24,3,15,3,6,3,0,8,10,8,10,1,21,13,10,28,11,27,17,1,13,10,11,4,36,26,4,2,2,2,10,0,11,5,22,6]
)

print(solution.solve.cache_info())

核心差异分析 #

两种思路的状态空间规模和计算逻辑复杂度完全不同，这是效率差距的根源：

• 高效解法的状态逻辑：
  状态是(i, members, cur_profit)，其中i代表当前处理到第i个犯罪。每个状态只做两种二元选择：跳过当前犯罪（递归到i+1），或者选择当前犯罪（如果人数足够，递归到i+1）。这种线性遍历+二元选择的方式，状态总数是O(len(group)*n*minProfit)，且大量不同路径会走到相同状态，缓存命中率高。

• 你的解法的状态逻辑：
  状态是(previous_crime_index, remaining_members, accumulated_profit)，其中previous_crime_index是上一次选择的犯罪索引。每个状态内部要循环遍历所有后续犯罪，相当于每个状态会触发len(group)-previous_crime_index-1个子状态。这会导致：

  1. 状态数量爆炸：当previous_crime_index较小时，循环要遍历大量后续犯罪，生成大量独特状态，即使这些状态的remaining_members和accumulated_profit相同，只要previous_crime_index不同，就无法复用缓存。
  2. 额外计算开销：每个状态内的循环本身就是耗时操作，再加上循环中额外的条件判断和加1操作，进一步增加了运行时间。

简单来说，高效解法是每一步做2种选择，状态数可控；你的解法是每一步做N种选择，状态数和计算量呈量级增长，最终导致效率差距。

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