加速使用动态规划的直接解决方案

Question

我最近遇到了以下问题:我们考虑以下数组:

A = [2, 3, 6, 1, 6, 4, 12, 24]

我们需要计算数组中满足这两个条件的次数:

A[i] * A[j] * A[k] = A[l] so that 0 <= i < j < k < l < len(A)

在这个例子中，的结果应该是8。数组中满足条件的示例:

2 * 3 * 1 = 6
2 * 6 * 1 = 12
6 * 1 * 4 = 24
3 * 1 * 4 = 12

我使用python创建的直接解决方案:

A = [2, 3, 6, 1, 6, 4, 12, 24]
result = 0
for i in range(len(A)):
for j in range(i + 1, len(A)):
for k in range(j + 1, len(A)):
for l in range(k + 1, len(A)):
if A[i] * A[j] * A[k] == A[l]:
result += 1
print(result)

我需要找到一种方法来加速程序使用动态，也许是记忆或预计算。

result = 0
for i in range(A):
for j in range(i + 1, A):
for k in range(j + 1, A):
#TODO
print(result)

我正在考虑创建一个字典，其中包含每个数字的一组字典，以指示数字及其位置，例如:

memo = {
6: {
2: True
4: True
}, 
1: {
3: True
},
...
}

则按如下方式检查:

result = 0
for i in range(A):
for j in range(i + 1, A):
for k in range(j + 1, A):
x = A[i] * A[j] * A[k]
if x in memo:
result += len([z[0] for z in memo[x].items() if z[0] > k])

通过这种方式，我们将一次计算索引k之后出现的所有相同数字，我们不必遍历整个数组。

请让我知道我的优化是有缺陷的，如果有更好的优化使用动态规划技术，如记忆或预计算。

Answer 1

我不是优化或动态规划方面的专家。但是你可以做什么来加速你的代码是使用itertools.combinations来事先确定所有的索引组合。这样，您只需在之后循环遍历所有组合。

下面的代码应该更快:

import itertools
# Determine combinations of indices
comb = itertools.combinations(range(len(A)),4)
result = 0
for idx in comb:
if A[idx[0]]*A[idx[1]]*A[idx[2]] == A[idx[3]]:
result += 1
result

显然，如果A是大尺寸的，这将不是一个快速的解决方案。但是对于你的数组，它要快2倍

Answer 2

一方面，似乎我们可以得到O(n^2 log n)通过哈希所有的对倍数和所有的对除法，其中除法是整数。对于倍数，存储一个仅包含每个这样的对的较高索引的列表;对于除法，存储一个仅包含每个这样的对的下标的列表。然后遍历每个除法对，并使用二分搜索来确定有多少对倍数匹配，谁的高索引更低。

A[i] * A[j] = A[l] / A[k]