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

Question

以下是一个面试问题,我无法以复杂性而非指数复杂性来回答这个问题.虽然它似乎是一个DP问题,但我无法形成基本案例并对其进行适当分析.任何帮助表示赞赏.

您将获得2个大小为'n'的数组.您需要稳定合并这些数组,以便在新数组中连续元素的乘积和最大化.

例如

A = {2,1,3}

B = {3,7,9}

在稳定合并A和B将给出一个带有'2n'元素的数组C,比如C = {c1,c2,c3,c4,c5,c6}你需要通过合并(稳定)A和B找到一个新的数组C,这样sum = c1*c2 + c3*c4 + c5*c6 ...... n是最大值.

Answer 1

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

c[i,j] 组成。

1. 最大值 = 最大值。
2. NeedsPairing = true 或 false = 取决于最左边的元素是否未配对。
3. Child = [p,q] 或 NULL = 定义子键，最终达到此级别的最佳总和。

现在定义该 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.Child 来追溯路径。