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

我需要写一个基于动态规划方法的算法，老实说，我完全陷入了困境。
好吧，问题是这样的我有两张同样长的单子比如说：

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])
显然，如果你选择了其中一种组合，你就不能再使用这些数字了。
我真正需要帮助的是找到递归函数我真的找不到。如果有人能帮我一把，我会非常感激的。
致意

最佳答案

这里的关键洞见是匹配是耦合的。如果将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

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

关于python - 两个列表的乘积的最大和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56063858/