동적 프로그래밍을 사용하여 중간 요소를 제거한 삼중 항 제품의 최소 합계

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

그러나이 솔루션은 더 작은 수의 경우에만 가능하지만 더 큰 수의 숫자는 가능하지 않습니다. 내가 찾고있는 것은 반복 동적 프로그래밍 접근법을 사용하여이를 수행하는 방법입니다.

Answer 1

DP에 필요한 최적 하부 구조는 제거 된 마지막 요소의 ID가 주어지면 왼쪽의 요소에 대한 제거 전략이 오른쪽 요소의 제거 전략과 독립적이라는 것입니다. 다음은이 관찰을 통합 (함께 질문의 버전과 두 개의 비교 테스트 하네스, 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에 대해 N choose 2 설정 만 다르며 메모를 메모하십시오. 실행 시간은 O(N^3)입니다. 사람이 다윗 Eisenstat의 재귀 솔루션을 기반으로 DP 솔루션에 관심이 있다면

Answer 2

, 여기 DP를 사용하여 반복이다 (많은 큰 숫자는 오랫동안의와 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]; 
}