Умножение цепочки матриц динамического программирования

Question

Я читал о умножении матричной цепочки в динамическом программировании, Он имеет наивное рекурсивное решение, которое имеет экспоненциальное время выполнения.

http://www.geeksforgeeks.org/dynamic-programming-set-8-matrix-chain-multiplication/

Хотя есть динамическая прог. решение (код в ссылке выше), который имеет сложность во времени выполнения O (n^3), но если мы сохраним 2d-массив для хранения результатов для перекрывающихся подпроцессов, будет ли он иметь такое же время выполнения, как и решение dp ?

public class MatrixChain { 

    public static void main(String... args) throws IOException { 
     new MatrixChain().job(); 
    } 

    private void job() { 
     int arr[] = new int[]{40, 20, 30, 10, 30}; 
     int[][] dp = new int[5][5]; 
     for (int[] x : dp) 
      Arrays.fill(x, -1); 
     int min = findMin(arr, 1, arr.length - 1, dp); 
     System.out.println(min); 
    } 

    private int findMin(int[] arr, int i, int j, int dp[][]) { 
     if (i == j) return 0; 
     int min = Integer.MAX_VALUE; 
     for (int k = i; k < j; k++) { 
      int fp; 
      if (dp[i][k] == -1) 
       dp[i][k] = fp = findMin(arr, i, k, dp); 
      else fp = dp[i][k]; 
      int lp; 
      if (dp[k + 1][j] == -1) 
       dp[k + 1][j] = lp = findMin(arr, k + 1, j, dp); 
      else 
       lp = dp[k + 1][j]; 

      int sum = fp + lp + arr[i - 1] * arr[k] * arr[j]; 
      if (sum < min) 
       min = sum; 
     } 
     return min; 
    } 
} 

Спасибо!

Answer 1

Да, это будет иметь. Неважно, пишете ли вы свою итеративную или рекурсивную функцию. Важно то, что вы запоминаете свои результаты. И что вы делаете.

Хотя у меня есть несколько оптимизаций:

private int findMin(int[] arr, int i, int j, int dp[][]) { 
    if (i == j) 
     return 0; 

    /* Immediate look-up in dp */ 
    if (dp[i][j] != -1) 
     return dp[i][j]; 

    /* Otherwise compute the number, much shorter since you don't 
     have to worry about reading from dp and saving it to dp. */ 
    int min = Integer.MAX_VALUE; 
    for (int k = i; k < j; k++) { 
     int fp = findMin(arr, i, k, dp); 
     int lp = findMin(arr, k + 1, j, dp); 
     int sum = fp + lp + arr[i - 1] * arr[k] * arr[j]; 
     if (sum < min) 
      min = sum; 
    } 

    /* Now save the result */ 
    dp[i][j] = min; 
    return min; 
}