Python编程题：解析f([1],1)=2测试用例及实现选数乘积计数函数

测试用例f([1], 1)返回2的原因 #

题目明确规定空序列的乘积为1，对于输入[1]，满足乘积等于目标值1的子集有两种：

• 空序列：乘积为1
• 选取列表中的数字1：乘积为1×1=1
  因此总共有2种有效方式，返回结果为2。
  同理，f([1,1,1],1)返回8是因为每个1都有“选”或“不选”两种选择，总共有2³=8个子集，所有子集的乘积均为1。

解题思路 #

核心思路是拆分问题，简化计算：

1. 单独处理数字1：选或不选1都不会改变乘积结果，因此最终有效方式数需要乘以2^count_1（count_1为列表中1的数量，每个1有两种选择）。
2. 动态规划计算非1数字的有效组合：使用动态规划字典dp，其中dp[p]表示选取若干非1数字相乘得到乘积p的方式数，初始状态dp[1] = 1（代表不选任何非1数字的方式）。遍历每个非1数字，更新dp字典，最终取dp[desired_product]作为非1数字的有效方式数。

代码实现 #

def f(numbers, desired_product):
    '''
    >>> f([2], 3)
    0
    >>> f([2, 3, 5], 11)
    0
    >>> f([1], 1)
    2
    >>> f([1, 1, 1], 1)
    8
    >>> f([2, 3], 2)
    1
    >>> f([1, 2, 3], 2)
    2
    >>> f([1, 2, 3], 6)
    2
    >>> f([3, 8, 7, 3, 7, 3, 7, 8, 5], 3 * 3 * 7)
    9
    >>> f([2, 5, 7, 11] * 4, 2 * 5 * 7)
    64
    >>> f([1, 2, 5, 7, 11] * 4, 2 * 5 * 7)
    1024
    >>> f(list(range(1, 10)), 40)
    4
    '''
    from collections import defaultdict

    # 统计列表中1的数量，并过滤出非1数字
    count_1 = numbers.count(1)
    non_ones = [num for num in numbers if num != 1]

    # 特殊情况：目标乘积为1，只能选1或空集
    if desired_product == 1:
        return 2 ** count_1

    # 动态规划字典：key为乘积值，value为对应方式数
    dp = defaultdict(int)
    dp[1] = 1  # 初始状态：不选任何非1数字

    for num in non_ones:
        # 跳过0（测试用例未涉及，若需处理可扩展逻辑）
        if num == 0:
            continue
        # 若当前数字大于目标且无法整除，选它不可能得到目标乘积，直接跳过
        if num > desired_product and desired_product % num != 0:
            continue
        # 反向遍历当前键，避免重复计算同一数字的多次选择
        current_keys = list(dp.keys())
        for p in reversed(current_keys):
            new_p = p * num
            if new_p == desired_product:
                dp[new_p] += dp[p]
            elif new_p < desired_product and desired_product % new_p == 0:
                dp[new_p] += dp[p]

    # 非1数字的有效方式数乘以1的可选组合数
    return dp.get(desired_product, 0) * (2 ** count_1)


if __name__ == '__main__':
    import doctest
    doctest.testmod()

测试用例验证 #

• f([3,8,7,3,7,3,7,8,5], 3*3*7)：需选2个3（3个3中选2个，共3种）和1个7（3个7中选1个，共3种），非1方式数为3×3=9，乘以2⁰得9，符合预期。
• f([2,5,7,11]*4, 2*5*7)：需选1个2（4种）、1个5（4种）、1个7（4种），非1方式数为4×4×4=64，乘以2⁰得64，符合预期。
• f([1,2,5,7,11]*4, 2*5*7)：非1方式数64，1的数量为4，2⁴=16，64×16=1024，符合预期。
• f(list(range(1,10)),40)：非1有效组合为{5,8}和{5,2,4}（共2种），1的数量为1，2¹=2，2×2=4，符合预期。

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