从两个数组增加序列

Question

给定两个相同长度 n 的整数列表 a 和 b。

找到严格递增的整数序列的计数，i[0] < i[1] < ... < i[n-1]使得

min(a[i], b[i]) <= i[i] <= max(a[i], b[i])对于每个i。

例子

输入：

a= [1,3,1,6]

b= [6,5,4,4]

输出：

4

这四个序列将是：

[1,3,4,5]

[1,3,4,6]

[2,3,4,5]

[2,3,4,5]

这是我试过的

a=[1,3,1,6]

b=[6,5,4,4]

P=[]

for i in range(len(a)):

    if i<len(a)-1:

        if max(a[i],b[i])>=max(a[i+1],b[i+1]):

            P.append([x for x in range(min(a[i],b[i]),min(max(a[i],b[i]),max(a[i+1],b[i+1])))])

        else:

            P.append([x for x in range(min(a[i],b[i]),1+min(max(a[i],b[i]),max(a[i+1],b[i+1])))])

    else:

        P.append([x for x in range(min(a[i],b[i]),max(a[i],b[i])+1)])

for i in range(len(a)):

    if i<len(a)-1 and P[i+1][-1]<=P[i][-1]:

        P[i]=[x for x in range(P[i][0],P[i+1][-1])]

    if i>0 and P[i][0]<=P[i-1][0]:

        P[i]=[x for x in range(P[i-1][0]+1,1+P[i][-1])

cnt=1

for i in P:

    cnt*=len(i)

print(cnt)

我所做的是我采用了这个设置

1 2 3 4 5 6

    3 4 5 

1 2 3 4

      4 5 6 

并将其减少到这个

1 2

   3 

    4 

      5 6 

删除所有不会进入序列的数字。

现在我要做的是，只需乘以每个行序列的 len。当有这样的情况时，问题就出现了。

1 2 3

    3 4

      4 5

        5 6 

现在长度的简单乘法不成立。这就是我被困的地方。

Answer 1

这是一种适合递归解决方案的问题，因此这里有一个可能的替代实现。（抱歉，我还没有尝试掌握您的代码，也许其他人会。）def sequences(a, b, start_index=0, min_val=None):&nbsp; &nbsp; """&nbsp; &nbsp; yields a sequence of lists of partial solutions to the original&nbsp; &nbsp; problem for sublists going from start_index to the end of the list&nbsp; &nbsp; subject to the constraint that the first value cannot be less than&nbsp; &nbsp; min_val (if not None)&nbsp; &nbsp; Example: with a=[3,4,5,6], b=[6,5,0,4], start_index=2, minval=4,&nbsp;&nbsp; &nbsp; it is looking at the [5,6] and the [0,4] part, and it would yield&nbsp; &nbsp; &nbsp;[4,5] [4,6] and [5,6]&nbsp; &nbsp; If the start index is not already the last one, then it uses a&nbsp; &nbsp; recursive call.&nbsp; &nbsp; """&nbsp; &nbsp; limits = a[start_index], b[start_index]&nbsp; &nbsp; lower = min(limits)&nbsp; &nbsp; higher = max(limits)&nbsp; &nbsp; if min_val is not None and min_val > lower:&nbsp; &nbsp; &nbsp; &nbsp; lower = min_val&nbsp; # impose constraint&nbsp; &nbsp; options = range(lower, higher + 1)&nbsp; &nbsp; is_last = start_index == len(a) - 1&nbsp; &nbsp; for val in options:&nbsp; &nbsp; &nbsp; &nbsp; if is_last:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield [val]&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # val followed by each of the lists from the recursive&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # callback - passing min_val=val+1 imposes the constraint&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; # of strictly increasing numbers&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for seq in sequences(a, b, start_index+1, min_val=val+1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield [val, *seq]for seq in sequences([1,3,1,6], [6,5,4,4]):&nbsp; &nbsp; print(seq)这给出：[1, 3, 4, 5][1, 3, 4, 6][2, 3, 4, 5][2, 3, 4, 6]请注意，我并不是说上面的方法特别有效：递归函数可能会使用相同的参数被调用不止一次——例如，无论您是从 1,3 还是 2,3 开始，它都会进行相同的计算来工作了解接下来会发生什么——因此您可能希望在将其用于大型列表之前实施某种缓存。显然，缓存有内存开销，因此制定最佳整体策略来应对这一问题可能是一个相当困难的问题。