按顺序使用算术运算符组合整数列表，求解最小不可表示正整数的高效方案问询

问题分析 #

你的递归思路方向是对的，但核心问题在于没有做记忆化处理，导致大量重复计算——相同的子数组会被反复递归处理，时间复杂度直接飙升到O(3ⁿ)，这在列表长度超过15时完全无法承受。

高效解决方案：动态规划（DP） #

我们可以用自底向上的动态规划思路，维护每个阶段能生成的正整数集合，彻底避免重复计算。核心逻辑如下：

• 定义dp[i]为处理前i个元素（即列表中nums[0]到nums[i-1]）时，能生成的所有正整数的集合。
• 从第一个元素开始，逐步推导后续每个阶段的结果：每一步都基于前一个阶段的集合，与当前元素进行三种运算（符合条件时），并只保留正整数结果。

代码实现 #

def find_smallest_unrepresentable(nums):
    n = len(nums)
    if n == 0:
        return 1
    
    # dp[i] 存储处理前i个元素能得到的所有正整数
    dp = [set() for _ in range(n + 1)]
    
    # 初始化：第一个元素如果是正整数，加入dp[1]
    first_num = nums[0]
    if first_num > 0:
        dp[1].add(first_num)
    
    # 逐步填充dp数组
    for i in range(2, n + 1):
        current_num = nums[i-1]
        # 遍历前i-1个元素的所有可能结果
        for val in dp[i-1]:
            # 加法运算，只保留正结果
            add_res = val + current_num
            if add_res > 0:
                dp[i].add(add_res)
            # 乘法运算，只保留正结果
            mul_res = val * current_num
            if mul_res > 0:
                dp[i].add(mul_res)
            # 整除运算：仅当除数不为0，且能整除，结果为正时才加入
            if current_num != 0 and val % current_num == 0:
                div_res = val // current_num
                if div_res > 0:
                    dp[i].add(div_res)
    
    # 从1开始找第一个无法表示的正整数
    smallest = 1
    while smallest in dp[n]:
        smallest += 1
    return smallest

为什么这个方法更高效？ #

1. 自动去重：用集合存储每个阶段的结果，自动过滤重复值，避免对同一个数值进行重复运算。
2. 无重复子问题：每个子问题（处理前i个元素）只计算一次，时间复杂度降为O(n*K)，其中K是每个dp[i]集合的平均大小——K远小于递归的指数级增长，因此能轻松处理长度超过15的列表。
3. 聚焦有效结果：只保留正整数结果，进一步缩小集合规模，提升运算速度。

测试示例 #

对于输入[1,2,3]：

• dp[1] = {1}
• dp[2] = {1+2=3, 1*2=2}
• dp[3] = {3+3=6, 3*3=9, 3//3=1, 2+3=5, 2*3=6} → 去重后为{1,5,6,9}
• 从1开始遍历，第一个不在集合中的正整数是2，与示例结果完全一致。

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