algorithm - 我怎么能算没有。元素乘积小于或等于数字 D 的子序列？

Question

我怎样才能算出没有。具有小于或等于数字 D 的元素乘积的数组的子序列，而不计算空子序列？

例如:

array=[2,2,2,3,4,10]
D=50
答案应该是 39。我试过回溯，但并没有那么快。数组中的所有数字都小于或等于D且大于0。

Answer 1

我的解决方案:

由于D比较小，所以我们把问题改成:

小于等于 D => 等于 X(X = 1 to D).

equal with X的解法:

define f(x,n) = the number of the ways to product to `x` by using first n numbers.

我们将得到:

f(x,n) = f(x, n-1) + f(x div a[n], n-1) (if x mod a[n] == 0)

结合内存，我们会得到一个O(D*n)的解。

代码如下:

__author__ = 'Sayakiss'

global a, mem

#a = [2, 2, 2, 3, 4, 10]
a = [2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 27, 29, 31, 101, 103]
mem = {}

def solve(x):
    sum = 0
    for i in range(1, x + 1):
        sum += f(i, len(a) - 1)
        #print str(i) + " " + str(f(i, len(a) - 1))
    return sum

def f(x, n):
    if x == 1:
        return 1
    if n == -1:
        return 0
    if mem.get((x, n)) is not None:
        return mem.get((x, n))
    result = 0
    if x % a[n] == 0:
        result += f(x / a[n], n - 1)
    result += f(x, n - 1)
    mem[(x, n)] = result
    return result

#print solve(50)
print solve(200000)

附言:

如果数组 a 中有任何 1，我的解决方案就会失败。但这很容易处理，所以你可以自己做。