Dynamic Programming21 sections · 916 units
Open in Course

D&C vs Knuth

When to use which

Use D&C when: DP has layers: dp[g][i]=min⁡j<i(dp[g−1][j]+cost(j,i))dp[g][i] = \min_{j < i}(dp[g-1][j] + cost(j, i)). Partitioning into kk groups. Use Knuth when: DP is interval-based: dp[i][j]=min⁡i≤k≤j(dp[i][k−1]+dp[k+1][j])+costdp[i][j] = \min_{i \leq k \leq j}(dp[i][k-1] + dp[k+1][j]) + cost. Combining subproblems. Both need: Cost satisfies the quadrangle inequality.

If unsure which, check the recurrence structure. Layers = D&C. Intervals = Knuth.