Proof of Correctness of Divide and Conquer Optimization

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

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

Follow the below section for proof of correctness:

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

• We have some indices 1 ≤ p ≤ q ≤ j and a separate fixed i. 
• Let dp_k[i][j] = cost[k][i] + dp[k-1][j-1]. 

If we can show that – 

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

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

Prrof:

From the Quadrangle inequality on the dp array we get –

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

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

This completes the proof dp_p[i][j] ≥ dp_q[i][j] ⇒ dp_p[i][j+1] ≥ dp_q[i][j+1]

Dynamic programming (DP) is arguably the most important tool in a competitive programmer’s repertoire. There are several optimizations in DP that reduce the time complexity of standard DP procedures by a linear factor or more, such as Knuth’s optimization, Divide and Conquer optimization, the Convex Hull Trick, etc. They are, of paramount importance for advanced competitive programming, such as at the level of olympiads. In this article, we will discover the divide and conquer optimization, NOT to be confused with the divide and conquer algorithm to solve problems.