DP Optimization: CHT, D&C, Knuth, SMAWK

DP Optimization, DP 최적화, DP optimization tricks

정의

일반 DP 를 O(N²) 또는 O(N³) 에서 O(N log N) 또는 O(N) 으로 낮추는 여러 최적화 기법의 총칭입니다. 모두 특정 조건 (monotone, concave, quadrangle inequality) 이 성립할 때만 적용 가능.

대표 4 종

1. Convex Hull Trick (CHT)

선형 함수 min/max 를 유지하는 자료구조. dp[i] = min(a[j]·x + b[j]) 형태에 적용.

• Li-Chao Tree: 임의 삽입 순서
• Kinetic: 온라인
• 모노톤 CHT: 기울기 정렬된 경우 O(1) push

전용 Li-Chao Tree 참조.

2. Divide-and-Conquer Optimization

dp[i][j] = min(dp[i-1][k] + cost(k, j)) 에서 최적 k 가 j 에 대해 단조 증가 하면 O(N²) → O(N log N).

function<void(int, int, int, int)> solve = [&](int lo, int hi, int optl, int optr) {
    if (lo > hi) return;
    int mid = (lo + hi) / 2;
    int best_k = optl;
    dp[mid] = LLONG_MAX;
    for (int k = optl; k <= min(mid, optr); k++) {
        long long cand = prev[k] + cost(k, mid);
        if (cand < dp[mid]) { dp[mid] = cand; best_k = k; }
    }
    solve(lo, mid - 1, optl, best_k);
    solve(mid + 1, hi, best_k, optr);
};

3. Knuth Optimization

dp[i][j] = min(dp[i][k] + dp[k][j]) + w(i, j) 형태. Quadrangle inequality + monotone 이면 O(N³) → O(N²).

행렬 곱셈 순서, 최적 이진 검색 트리, LP 등.

4. SMAWK / Monge

Monge 행렬 (모든 2×2 부분행렬이 QI 만족) 위 행별 최솟값을 O(N) 에 계산.

참고

• Li-Chao Tree
• DP Bitfield
• Knapsack DP