The smallest amount of triplet products, where the middle element is removed using dynamic programming

Question

I gave a sequence of N numbers (4 ≤ N ≤ 150). One index i (0 <i <N) is selected and multiplied by the left and right numbers, in other words, with i-1 and i + 1. Then the i-th number is deleted. This is done until only two numbers remain in the sequence. The goal is to find the smallest sum of these products, which obviously depends on the order in which the indices are selected.

eg. for a sequence of 44, 45, 5, 39, 15, 22, 10, the smallest sum will be equal to 17775 using indices in the following order: 1-> 3-> 4-> 5-> 2, which is the sum: 44 * 45 * 5 + 5 * 39 * 15 + 5 * 15 * 22 + 5 * 22 * ​​10 + 44 * 5 * 10 = 9900 + 2925 + 1650 + 1100 + 2200 = 17775

I found a solution using a recursive function:

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;
    }
}

However, this solution is possible only for small N, but not for a larger number of numbers. What I'm looking for is a way to do this using an iterative approach to dynamic programming.

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 memoize. O(N^3).

Answer 2

- DP, , DP ( int long):

public static int smallestSum(List<Integer> values) {
    int[][] table = new int[values.size()][values.size()];

    for (int i = 2; i < values.size(); i++) {
        for (int j = 0; j + i < values.size(); j++) {
            int ret = Integer.MAX_VALUE;

            for (int k = j + 1; k <= j + i - 1; k++) {
                int val = table[j][k] + values.get(j) * values.get(k) * values.get(j + i) + table[k][j + i];
                if (val < ret) ret = val;
            }

            table[j][j + i] = ret;
        }
    }

    return table[0][values.size() - 1];
}