ダイナミックプログラミングを使用して中間要素が削除されたトリプレット積の最小合計

Question

私はN個の数値のシーケンスを与えました（4≦N≦150）。 1つのインデックスi（0 < i < N）がピックされ、左と右の数、つまりi-1とi + 1で乗算されます。次にi番目の番号が削除されます。これは、シーケンスに2つの数字だけが残るまで実行されます。目指すのは、これらの製品の最小の合計を見つけることです。これは明らかに、インデックスが選択される順序に依存します。

など。シーケンス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に必要な最適な部分構造は、削除された最後の要素の識別情報が与えられている場合、左側の要素の削除戦略は右側の要素の削除方法とは無関係です。ここでは、この観察を取り入れた（一緒に質問からバージョンと2の比較テストハーネスで、smallestSumA）新しい再帰関数です：smallestSum(values, 0, values.size() - 1)として

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

を呼び出します。

DPを取得するには、firstとlastの異なる設定があり、メモを設定するだけであることに注意してください。実行時間はO(N^3)です。

Answer 2

誰もがDPソリューションに興味がある場合は、デビッドEisenstatの再帰的なソリューションに基づいて、ここでDPを使用して、反復1（多くの大きな数字のために、それは長いのでint型のを置き換えるために便利です）です：

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