稳定合并两个阵列以最大化相邻元素的乘积

Question

以下是一个采访问题，我无法回答的复杂性低于指数复杂性。虽然这似乎是一个DP问题，但我无法形成基本案例并正确分析它。感谢您的帮助。

将为您提供两个大小为“n”的数组。您需要稳定地合并这些数组，以便在新数组中使连续元素的乘积之和最大化。

例如

A={2,1,5}

B={3,7,9}

稳定合并A={a1，a2，a3}和B={b1，b2，b3}将创建一个包含2*n个元素的数组C。例如，通过合并（稳定的）A和B，假设C={b1，a1，a2，a3，b2，b3}。那么和=b1*a1 a2*a3 b2*b3应该是最大值。

Answer 1

我的解决办法相当简单。我只是探索所有可能的稳定合并。遵循工作C程序：

#include<iostream>

using namespace std;

void find_max_sum(int *arr1, int len1, int *arr2, int len2, int sum, int& max_sum){
  if(len1 >= 2)
    find_max_sum(arr1+2, len1-2, arr2, len2, sum+(arr1[0]*arr1[1]), max_sum);
  if(len1 >= 1 && len2 >= 1)
    find_max_sum(arr1+1, len1-1, arr2+1, len2-1, sum+(arr1[0]*arr2[0]), max_sum);
  if(len2 >= 2)
    find_max_sum(arr1, len1, arr2+2, len2-2, sum+(arr2[0]*arr2[1]), max_sum);
  if(len1 == 0 && len2 == 0 && sum > max_sum)
    max_sum = sum;
}

int main(){
  int arr1[3] = {2,1,3};
  int arr2[3] = {3,7,9};
  int max_sum=0;
  find_max_sum(arr1, 3, arr2, 3, 0, max_sum);
  cout<<max_sum<<endl;
  return 0;
}

Answer 2

对于A={a1， a2，...， an}， B={b1， b2，...， bn}，

定义DP[i，j]为{ai，…，an}和{bj，…，bn}之间的最大稳定合并和。

（一）

DP[n 1， n 1]=0， DP[n 1， k]=bk*bk 1... bn-1*bn， DP[k， n 1]=ak*ak 1... an-1*an.

DP[n，k]=max{an*bk bk 1*bk 2..bn-1*bn，DP[n，k 2]bk*bk 1}

DP[k，n]=max{ak*bn ak 1*ak 2..an-1*an，DP[k2，n]ak*ak 1}

DP[i，j]=max{DP[i2，j]ai*ai1，DP[i，j2]bi*bi1，DP[i1，j1]ai*bi}。

然后返回DP[1,1]。

说明：在每一步中，你必须考虑3个选项：从剩下的A中取前2个元素，从剩下的B中取第一个2个元素，或者从A和B中取两个元素（因为你不能改变A和B的顺序，你必须从A和B中取第一个）。

Answer 3

让我们定义c[i， j]作为相同问题的解，但是数组从i开始到左结束。和j以右结尾。所以c[0,0]将给出原始问题的解。

c[i，j]包括。

1. MaxValue=最大值

现在定义这个DP的最优子结构

c[i,j] = if(NeedsPairing) { left[i]*right[j] } + Max { c[i+1, j], c[i, j+1] }

在此代码中更详细地捕获了它。

if (lstart == lend)
{
    if (rstart == rend)
    {
        nodeResult = new NodeData() { Max = 0, Child = null, NeedsPairing = false };
    }
    else
    {
        nodeResult = new NodeData()
        {
            Max = ComputeMax(right, rstart),
            NeedsPairing = (rend - rstart) % 2 != 0,
            Child = null
        };
    }
}
else
{
    if (rstart == rend)
    {
        nodeResult = new NodeData()
        {
            Max = ComputeMax(left, lstart),
            NeedsPairing = (lend - lstart) % 2 != 0,
            Child = null
        };
    }
    else
    {
        var downLef = Solve(left, lstart + 1, right, rstart);

        var lefResNode = new NodeData()
        {
            Child = Tuple.Create(lstart + 1, rstart),
        };

        if (downLef.NeedsPairing)
        {
            lefResNode.Max = downLef.Max + left[lstart] * right[rstart];
            lefResNode.NeedsPairing = false;
        }
        else
        {
            lefResNode.Max = downLef.Max;
            lefResNode.NeedsPairing = true;
        }

        var downRt = Solve(left, lstart, right, rstart + 1);

        var rtResNode = new NodeData()
        {
            Child = Tuple.Create(lstart, rstart + 1),
        };

        if (downRt.NeedsPairing)
        {
            rtResNode.Max = downRt.Max + right[rstart] * left[lstart];
            rtResNode.NeedsPairing = false;
        }
        else
        {
            rtResNode.Max = downRt.Max;
            rtResNode.NeedsPairing = true;
        }

        if (lefResNode.Max > rtResNode.Max)
        {
            nodeResult = lefResNode;
        }
        else
        {
            nodeResult = rtResNode;
        }
    }
}

我们使用记忆来防止再次解决子问题。

Dictionary<Tuple<int, int>, NodeData> memoization = new Dictionary<Tuple<int, int>, NodeData>();

最后我们使用NodeData。要追溯路径的子对象。