我有一个这样的数字列表（随机生成，数字在每个子组中排序。这些组是不相交的，这意味着您不会在多个组中找到给定的数字）：
L=[[19,18,14,9,4],[15,12,11,10,6,5],[8],[16,13,3,2],[17,7,1]]
我正在尝试计算创建三重递减的方法的数量。
递减三元组是一个三元组，其中我们从左到右扫描列表，然后从一组中拔出元素1，然后从另一组中拔出元素2，然后从另一组中拔出元素3，最终结果自然应该是降序排列。
例如，（19,11,7）是有效的递减三元组，因为这些数字来自不同的子列表，并且以递减的自然顺序排列（19在主列表之前排在11之前，在11之后排在第七）。
用反例进行说明：（15，9，8）不会减少三元组，因为9来自早于15的子列表。
我试图使用动态编程或某种形式的备忘来计算减少三胞胎的数量。像这样建立一个循环结构是很容易的：
for i in xrange(0,len(L)-2):
for j in xrange(i+1, len(L)-1):
for k in xrange(j+1, len(L)):
for item1 in L[i]:
for item2 in L[j]:
if item1>item2:
for item3 in L[k]:
if item2>item3:
count+=1
但是对于较大的列表，它的伸缩性不是很好。我觉得应该有一些方法可以通过一次浏览列表来计算三胞胎。例如，如果我知道一个数字大于另一个数字（或者如果我知道该数字大于另一个数字），我觉得我以后应该能够重用该信息。
例如，我知道在有效的三元组中16可以排在7或1之前。那是2对。因此，如果我想在列表中向后移动时创建一个三元组，而我看到19，我应该能够说“它大于16，因此您可以据此创建两个三元组，因为我们知道16比2大。”等等。
我只是大声思考，但希望能有所启发。
最佳答案
在i和0之间使用索引n而不是嵌套循环。
跟踪当前三元组的最后一个元素。
并使用备忘录以使其高效。
L=[[19,18,14,9,4],[15,12,11,10,6,5],[8],[16,13,3,2],[17,7,1]]
n=len(L)
memo = {}
def f(i,j,last):
if (i,j,last) in memo:
return memo[(i,j,last)]
if j==3:
return 1
if i==n:
return 0
res=0
# take one from L[i]
for x in L[i]:
if last > x:
res+=f(i+1,j+1,x)
# don't take any element from L[i]
res += f(i+1,j,last)
memo[(i,j,last)] = res
return res
BIG = 10**9
print f(0,0,BIG)
关于c++ - 动态编程/内存(三胞胎计数)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10147423/