java - 使用动态规划删除中间元素的三重乘积的最小总和

Question

我已经给出了 N 个数字的序列 (4 ≤ N ≤ 150)。选择一个索引 i (0 < i < N) 并与左右数相乘，换句话说，与 i-1 和 i+1 相乘。然后删除第 i 个数字。这样做直到序列只剩下两个数字。目标是找到这些产品的最小总和，这显然取决于选择指数的顺序。

例如对于序列 44、45、5、39、15、22、10，最小的总和为 17775 按以下顺序使用索引:1->3->4->5->2 这是总和: 44*45*5 + 5*39*15 + 5*15*22 + 5*22*10 + 44*5*10 = 9900 + 2925 + 1650 + 1100 + 2200 = 17775

我找到了一个使用递归函数的解决方案:

public static int smallestSum(List<Integer> values) {
    if (values.size() == 3)
        return values.get(0) * values.get(1) * values.get(2);
    else {
        int ret = Integer.MAX_VALUE;

        for (int i = 1; i < values.size() - 1; i++) {
            List<Integer> copy = new ArrayList<Integer>(values);
            copy.remove(i);

            int val = smallestSum(copy) + values.get(i - 1) * values.get(i) * values.get(i + 1);
            if (val < ret) ret = val; 
        }

        return ret;
    }
}

但是，这种解决方案只适用于小 N，而不适用于更大数量的数字。我正在寻找的是一种使用迭代动态编程方法来执行此操作的方法。

Answer 1

DP 所需的最佳子结构是，给定最后删除的元素的标识，左侧元素的消除策略独立于右侧元素的消除策略。这是一个新的递归函数(smallestSumA，以及问题的版本和比较两者的测试工具)结合了这一观察:

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Foo {
  public static void main(String[] args) {
    Random r = new Random();
    for (int i = 0; i < 10000; i++) {
      List<Integer> values = new ArrayList<Integer>();
      for (int n = 3 + r.nextInt(8); n > 0; n--) {
        values.add(r.nextInt(100));
      }
      int a = smallestSumA(values, 0, values.size() - 1);
      int q = smallestSumQ(values);
      if (q != a) {
        System.err.println("oops");
        System.err.println(q);
        System.err.println(a);
        System.err.println(values);
      }
    }
  }

  public static int smallestSumA(List<Integer> values, int first, int last) {
    if (first + 2 > last)
      return 0;
    int ret = Integer.MAX_VALUE;
    for (int i = first + 1; i <= last - 1; i++) {
      int val = (smallestSumA(values, first, i)
          + values.get(first) * values.get(i) * values.get(last) + smallestSumA(values, i, last));
      if (val < ret)
        ret = val;
    }
    return ret;
  }

  public static int smallestSumQ(List<Integer> values) {
    if (values.size() == 3)
      return values.get(0) * values.get(1) * values.get(2);
    else {
      int ret = Integer.MAX_VALUE;

      for (int i = 1; i < values.size() - 1; i++) {
        List<Integer> copy = new ArrayList<Integer>(values);
        copy.remove(i);

        int val = smallestSumQ(copy) + values.get(i - 1) * values.get(i) * values.get(i + 1);
        if (val < ret)
          ret = val;
      }

      return ret;
    }
  }
}

调用为 smallestSum(values, 0, values.size() - 1)。

要获得 DP，请观察 N choose 2 first 和 last 的不同设置，然后内存。运行时间为 O(N^3)。