python - 代码优化-组合数量

Question

给定一个数字C(C是一个整数)，并给定一个数字列表(我们称之为N，列表N中的所有数字都是整数)。 我的任务是找出代表 C 的可能性的数量。

例如:

输入:

C = 4

N = [1, 2]

输出:

3

因为:

4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 2 + 2

我的代码对于少量数据运行得很好。但是我不知道如何优化它，以便它也适用于更大的整数。任何帮助将不胜感激!

这是我的代码:

import numpy
import itertools
def amount(C):
    N = numpy.array(input().strip().split(" "),int)
    N = list(N)
    N = sorted(N)
    while C < max(N):
        N.remove(max(N))
    res = []
    for i in range(1, C):
        for j in list(itertools.combinations_with_replacement(N, i)):
            res.append(sum(list(j)))
    m = 0
    for z in range (0, len(res)):
        if res[z] == C:
            m += 1
    if N[0] == 1:
        return m + 1 
    else:
        return m 

Answer 1

您的算法的复杂度是O(len(a)^С)。要更有效地解决此任务，请使用 dynamic programming想法。

假设dp[i][j]等于使用术语a[0]、a[1]、...的i的分区数，a[j]。数组 a 不应包含重复项。该解决方案的运行时间为O(C * len(a)^2)。

def amount(c):
    a = list(set(map(int, input().split())))

    dp = [[0 for _ in range(len(a))] for __ in range(c + 1)]
    dp[0][0] = 1

    for i in range(c):
        for j in range(len(a)):
            for k in range(j, len(a)):
                if i + a[k] <= c:
                    dp[i + a[k]][k] += dp[i][j]

    return sum(dp[c])