Advanced Dynamic Programming
Digit DP, bitmask DP, subset DP, tree DP, rerooting DP, interval DP, profile DP, probability DP, SOS DP, DP optimization, convex hull trick, Li Chao tree, divide-and-conquer optimization, Knuth optimization, and monotonic queue optimization.
Every optimization lesson must list the required recurrence form and preconditions.
dp[i] = min_(j ∈ [i−k, i)) (dp[j]) + c[i] window of candidates slides O(nk) → O(n) Convex hull trick dp[i] = min_j (m_j·x_i + b_j) slopes monotone and queries monotone (or use Li Chao) O(n²) → O(n) / O(n log n) same, arbitrary insertion order lines over a known x range O(log C) per op Divide and conquer
dp[k][i] = min_(j<i) dp[k−1][j] + C(j, i) optimal j is monotone in i (opt[i] ≤ opt[i+1]) O(kn²) → O(kn log n)
dp[i][j] = min_(i<k<j) dp[i][k] + dp[k][j] + C(i, j) C satisfies the quadrangle inequality and monotonicity, so opt[i][j−1] ≤ opt[i][j] ≤ opt[i+1][j] O(n³) → O(n²) f[mask] = Σ_(sub ⊆ mask) a[sub] O(3ⁿ) → O(n·2ⁿ) count numbers ≤ N with a digit property property decomposes digit by digit O(N) → O(digits · states)
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
The convex hull trick rewrites dp[j] + (xᵢ − xⱼ)² + C as xᵢ² + C + min_j (−2xⱼ·xᵢ + dp[j] + xⱼ²): a minimum over lines evaluated at xᵢ. With slopes added in decreasing order and queries increasing, a deque keeps only the lower envelope, giving O(n). The bad test decides whether the middle line is ever the minimum; it uses __int128 because the products exceed long long. Digit DP carries (position, digit-sum mod 7, tight); tight records whether the prefix still equals N's prefix, which limits the next digit.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// digit DP: how many numbers in [0, N] have digit sum divisible by 7?
ll digitCount(ll N) {
string s = to_string(N);
vector<vector<vector<ll>>> memo(s.size(), vector<vector<ll>>(7, vector<ll>(2, -1)));
function<ll(size_t, int, bool)> go = [&](size_t pos, int mod, bool tight) -> ll {
if (pos == s.size()) return mod == 0;
ll& m = memo[pos][mod][tight];
if (m != -1) return m;
ll r = 0; int limit = tight ? s[pos] - '0' : 9;
for (int d = 0; d <= limit; ++d) r += go(pos + 1, (mod + d) % 7, tight && d == limit);
return m = r;
};
return go(0, 0, true);
}
// convex hull trick (monotone slopes and queries): dp[i] = min_j dp[j] + (x_i - x_j)^2 + C
ll chtSolve(const vector<ll>& x, ll C) {
int n = (int)x.size(); vector<ll> dp(n, 0);
deque<pair<ll, ll>> hull; // lines y = m*q + b, slopes decreasing
auto bad = [](pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) { return (__int128)(c.second - a.second) * (a.first - b.first) <= (__int128)(b.second - a.second) * (a.first - c.first); };
auto value = [](pair<ll,
…numbers in [0, 1000000] with digit sum divisible by 7: digit DP 142880, brute force 142880
digit DP for N = 10^18: 142857142856594042 (brute force impossible)
convex hull trick matches the O(n^2) DP on 200 random cases; n = 200000 solved: 133583635Quiz
? What does the `tight` flag in digit DP record?
+ Whether the digits chosen so far equal N's prefix, which limits the next digit :: Once below N, every later digit is free.
- Whether the number is prime :: No.
- The current digit sum :: That is the `mod` state.
- Whether memoisation is allowed :: Memo stores both values.
? Which precondition allows divide-and-conquer DP optimisation?
+ The optimal split point opt[i] is monotone in i :: Then each level of recursion is O(n).
- The cost function is linear :: Not required.
- The DP has one dimension :: It typically has two (k, i).
- Values are integers :: Irrelevant.
? Why must you verify preconditions before applying an optimisation like Knuth's?
+ Without them the restricted search can skip the true optimum and give a wrong answer :: “Looks similar” is not enough.
- The code will not compile otherwise :: It compiles and silently errs.
- They only affect speed :: They affect correctness.
- Optimisations always apply :: No.