Knuth’s Optimization in Dynamic Programming

Knuth’s optimization is a very powerful tool in dynamic programming, that can be used to reduce the time complexity of the solutions primarily from O(N³) to O(N²). Normally, it is used for problems that can be solved using range DP, assuming certain conditions are satisfied. In this article, we will first explore the optimization itself, and then solve a problem with it.

Optimization Criteria:

Knuth’s optimization is applied to DP problems with a transition of the following form –

dp[i][j] = cost[i][j] + min_i≤k<j(dp[i][k] + dp[k+1][j])

Further, the cost function must satisfy the following conditions (for a ≤ b ≤ c ≤ d) –

1. It is a Monotone on the lattice of intervals (MLI) [cost(b, c) ≤ cost(a, d)]
2. It satisfies the quadrangle inequality (QI) [cost(a, c) + cost(b, d) ≤ cost(b, c) + cost(a, d)]

Optimization:

For a solution that runs in O(N³) time, we would iterate through all values of k from i to j-1. However, we can do better than this using the following optimization:

• Let’s define another array in addition to the dp array – opt[N][N]. Define opt[i][j] as the maximum (or minimum) value of k for which dp[i][j] is minimized in the dp transition.
  opt[i][j] = argmin_i≤k<j(dp[i][k] + dp[k+1][j])
• The key to Knuth’s optimization, and several other optimizations in DP such as the Divide and Conquer optimization (not to be confused with the divide and conquer algorithm explained in this article), is the following inequality –

opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]

• This helps because now, for each dp[] transition to calculate dp[i][j], we only have to test values of k between opt[i][j-1] and opt[i+1][j] instead in between i to j-1. This reduces the time complexity of the algorithm by a linear factor, which is a significant improvement.

Proof of Correctness:

To prove the correctness of this algorithm, we only need to prove the inequality: 

opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j].

Follow the below section for the proof of the correctness of the algorithm:

Assumptions: If cost(i, j) is an MLI and satisfies the Quadrangle Inequality, then dp[i][j] also satisfies the inequality.  
Now, consider the following setup – 

• For i < j, we have some indices i ≤ p ≤ q < j-1. 
• Let dp_k[i][j] = cost[i][j] + dp[i][k] + dp[k+1][j]. 

If we can show that:

dp_p[i][j-1] ≥ dp_q[i][j-1] ⇒ dp_p[i][j] ≥ dp_q[i][j] 

then setting q = opt[i][j-1], it will be clear that opt[i][j] will be at least as much as opt[i][j-1], due to the implication of the above inequality for all indices p less than opt[i][j-1]. 
This will prove that opt[i][j-1] ≤ opt[i][j].

Proof: Using the quadrangle inequality on the dp array, we get –

dp[p+1][j-1] + dp[q+1][j] ≤ dp[q+1][j-1] + dp[p+1][j]
⇒ (dp[i, p] + dp[p+1][j-1] + cost(i, j-1)) + (dp[i, q] + dp[q+1][j] + cost(i, j))
     ≤ (dp[i, q] + dp[q+1][j-1] + cost(i, j-1)) + (dp[i, p] + dp[p+1][j] + cost(i, j))
⇒ dp_p[i][j-1] + dp_q[i][j] ≤ dp_p[i][j] + dp_q[i][j-1]
⇒ dp_p[i][j-1] – dp_q[i][j-1] ≤ dp_p[i][j] – dp_q[i][j]

dp_p[i][j-1] ≥ dp_q[i][j-1] 
⇒ 0 ≤ dp_p[i][j-1] – dp_q[i][j-1] ≤ dp_p[i][j] – dp_q[i][j] 
⇒ dp_p[i][j] ≥ dp_q[i][j]. 

Hence it is proved that: dp_p[i][j-1] ≥ dp_q[i][j-1] ⇒ dp_p[i][j] ≥ dp_q[i][j]

The second part of the inequality (i.e. opt[i][j] ≤ opt[i+1][j]) can be shown with the same idea, starting with the inequality

dp[i][p]+dp[i+1][q] ≤ dp[i][q]+dp[i+1][p].

The proof of these two inequalities combinedly gives: opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]

Example:

Given an array arr[] of N elements, the task is to find the minimum cost for reducing the array to a single element in N-1 operations where in each operation: 

• Delete the elements at indices i and i+1 for some valid index i, replacing them with their sum. 
• The cost of doing so is arr[i] + arr[i+1], where arr[] is the array state just before the operation.
• This cost will be added to the final cost.

Examples: 

Input: arr[] = {3, 4, 2, 1, 7}
Output: 37
Explanation: 
Remove the elements at 0th and 1st index. arr[] = {7, 2, 1, 7}, Cost = 3 + 4 = 7
Remove 1st and 2nd index elements. arr[] = {7, 3, 7}, Cost = 2 + 1 = 3
Remove 1st and 2nd index elements, arr[] = {7, 10}, Cost = 3 + 7 = 10
Remove the last two elements. arr[] = {17}, Cost =  = 7 + 10 = 17
Total cost = 7 + 3 + 10 + 17 = 37
This is the minimum possible total cost for this array.

Input: arr[] = {1, 2, 3, 4}
Output: 19
Explanation: 
Remove the 0th and 1st index elements. arr[] = {3, 3, 4}. Cost = 1 + 2 = 3
Remove the 0th and 1st index elements. arr[] = {6, 4}. Cost = 3 + 3 = 6
Remove the 0th and 1st index elements. arr[] = {10}. Cost = 6 + 4 = 10
Total cost = 3 + 6 + 10 = 19.
This is the minimi=um possible cost.

Sub-optimal solution (using Range DP): The problem can be solved using the following idea: 

• Let arr[] be the original array before any modifications are made. 
• For an element in the array that has been derived from indices i to j of a[], the cost of the final operation to form this single element will be the sum arr[i] + arr[i+1] + . . . + arr[j]. Let this value be denoted by the function cost(i, j).
• To find the minimum cost for the section arr[i, i+1, … j], consider the cost of converting the pairs of sub-arrays arr[i, i+1 . . . k] & arr[k+1, k+2 . . . j] into single elements, and choose the minimum over all possible values of k from i to j-1 (both inclusive).

For implementing the above idea:

• The cost function can be calculated in constant time with preprocessing, using a prefix sum array:
  • Calculate prefix sum (say stored in pref[] array).
  • So cost(i, j) can be calculated as (pref[j] – pref[i-1]).
• Traverse from i = 0 to N-1:
  • Traverse j =  i+1 to N-1 to generate all the subarray of the main array:
    • Solve this problem for all these possible subarrays with the following dp transition – 
      dp[i][j] = cost(i, j) + min_i≤k≤j-1(dp[i][k] + dp[k+1][j]) as explained in the above idea.
• Here dp[i][j] is the minimum cost of applying (j – i) operations on the sub-array arr[i, i+1, . . . j] to convert it to a single element. 
  cost(i, j) denotes the cost of the final operation i.e. the cost of adding the last two values to convert arr[i, i+1, . . ., j] to a single element.
• The final answer will be stored on dp[0][N-1].

Below is the implementation of the above approach.

37

Time complexity: O(N³)
Auxiliary Space: O(N²) 

Optimal solution (using Knuth’s optimization):

The conditions for applying Knuth’s optimization hold for this question:

cost(i, j) is merely the sum of all elements in the subarray bounded by the indices i and j. Further, the transition function of dynamic programming matches the general case for applying this technique.

Follow the steps mentioned here to implement the idea of Knuth optimization:

• Define the array opt[N][N] and the dp[][] array. 
• Now, process subarrays in increasing order of length, with the initial state dp[i][i] = 0, and opt[i][i] = i (because the value should be i to minimize the value dp[i][i]).
• Thus, when we reach the subarray arr[i, . . ., j], the value of opt[i][j-1] and opt[i+1][j] are already known. So, only check for the condition opt[i][j-1] ≤ k ≤ opt[i+1][j], to find opt[i][j] and dp[i][j]. 
• Here also the cost function is calculated in the same way as in the previous approach using the prefix sum array.

Note: In the code given below different way of looping through all sub-arrays is used (instead of looping in increasing order of length), However, ensuring that opt[i+1][j] and opt[i][j-1] are calculated before dp[i][j].

Below is the implementation of the above approach. 

37

Time Complexity: O(N²)
Auxiliary Space: O(N²)