python - 两个列表的最大乘积和

Question

我需要编写一个基于动态规划方法的算法，老实说，我完全卡住了。

好的，问题就是这样。我有两个长度相同(偶数)的列表。例如，假设:

a = [43, 10, 40, 12]
b = [63, 73, 5,  13]

我需要使用动态规划方法从这些列表中找到成对数字乘积的最大和。这些数字只能按照以下方式配对:

(a[n] * a[n+1]) V (b[n] * b[n+1]) V (a[n] * b[n])

显然，如果您选择了其中一种组合，您将无法再使用这些数字。

我真正需要帮助的是找到它的递归函数。而我真的找不到。如果有人能帮助我，我将不胜感激。

最好的问候

Answer 1

这里的关键见解是匹配是耦合的。如果你将 a[i] 匹配到 a[i+1]，你还必须将 b[i] 匹配到 b [i+1]。否则，至少会有一个不匹配的条目。因此，当您从左到右遍历列表时，您只需决定是垂直匹配还是水平匹配。

为了将其表述为动态程序，我们传播了函数 S(i)，该函数记录了使用元素 0 .. i 可以获得的最大分数。那么递归关系是:

S(i) = max(
            S(i - 1) + a[i] * b[i],                        #vertical match
            S(i - 2) + a[i - 1] * a[i] + b[i - 1] * b[i])  #horizontal match

当然，有适当的边界处理。