#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/d-c-and-knuth-optimization/ciel-and-gondola-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/d-c-and-knuth-optimization/ciel-and-gondola-implementation

Repovive

Codeforces 321E Ciel and Gondola - Implementation - D&C and Knuth Optimization | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Codeforces 321E Ciel and Gondola - Implementation

The code

Here's the D&C solution:

function solve(g, l, r, optL, optR, dp, cost)
    if l > r then
        return
    mid := (l + r) / 2
    opt := optL
    dp[g][mid] := infinity
    for j from optL to min(optR, mid - 1)
        val := dp[g-1][j] + cost[j+1][mid]
        if val < dp[g][mid] then
            dp[g][mid] := val
            opt := j
    solve(g, l, mid-1, optL, opt, dp, cost)
    solve(g, mid+1, r, opt, optR, dp, cost)
    // Each layer g: solve(g, 1, n, 0, n-1, dp, cost)

Time: $O(k \cdot n \log n)$ . Precompute $cost$ in $O(n^2)$ . The QI property guarantees that optimal splits are monotonic, enabling the Knuth improvement.

Space: $O(n \cdot k)$ for the DP table.

Time: $O(n \cdot k \log n)$ . Space: $O(n \cdot k)$ .