Linear DP

Longest Increasing Subsequence (LIS)

Achieves O(n log n) time complexity using binary search:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> seq(n);
    for (auto &x : seq) cin >> x;

    vector<long long> tail;
    for (long long val : seq) {
        auto it = lower_bound(tail.begin(), tail.end(), val);
        if (it == tail.end()) {
            tail.push_back(val);
        } else {
            *it = val;
        }
    }
    cout << tail.size() << '\n';
    return 0;
}

Longest Common Increasing Subsequence (LCIS)

Runs in O(n2) time using dynamic programming with careful state transitions and optimization via auxiliary arrays.

Count of LIS

Requires tracking both length and count per position; typically solved by extending LIS DP with an additional dpCount array and handling multiple paths.

Interval DP

Turning Off the Lamps

Given n lamps at positions ai with power consumption rates wi, starting at position m, minimize total energy consumed while turning off all lamps.

DP state: f[l][r][0/1] represents the minimum extra energy needed after switching off lamps in interval [l, r], ending at left (0) or right (1) end.

Prefix sums on energy help compute passive consumption during movement.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, start;
    cin >> n >> start;
    vector<int> pos(n + 1), rate(n + 1);
    vector<long long> prefix(n + 1);

    for (int i = 1; i <= n; ++i) {
        cin >> pos[i] >> rate[i];
        prefix[i] = prefix[i - 1] + rate[i];
    }

    vector<vector<vector<long long>>> dp(n + 2, vector<vector<long long>>(n + 2, vector<long long>(2, 1e18)));
    dp[start][start][0] = dp[start][start][1] = 0;

    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;

            // Ending at left (l), came from l+1 (left) or r (right)
            long long costL_left = dp[l+1][r][0] + (pos[l+1] - pos[l]) * (prefix[l] + prefix[n] - prefix[r]);
            long long costL_right = dp[l+1][r][1] + (pos[r] - pos[l]) * (prefix[l] + prefix[n] - prefix[r]);
            dp[l][r][0] = min(costL_left, costL_right);

            // Ending at right (r), came from r−1 (right) or l (left)
            long long costR_right = dp[l][r-1][1] + (pos[r] - pos[r-1]) * (prefix[r-1] + prefix[n] - prefix[l-1]);
            long long costR_left = dp[l][r-1][0] + (pos[r] - pos[l]) * (prefix[r-1] + prefix[n] - prefix[l-1]);
            dp[l][r][1] = min(costR_right, costR_left);
        }
    }

    cout << min(dp[1][n][0], dp[1][n][1]) << '\n';
    return 0;
}

Ring DP (Circular Conventions)

Maximum Subarray Sum in Circular Array

Consider two cases:

• Non-wrapping: Standard Kadane’s algorithm.
• Wrapping: Total sum minus minimum subarray sum.

Using deque-based monotonic queue for sliding-window maximum/minimum degradation helps in related problems like "Sliding Window".

Tree DP

Maximum Subtree Sum

DFS traversal computes dp[node] = node_value + sum of child contributions (if positive).

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> val(n + 1);
    for (int i = 1; i <= n; ++i) cin >> val[i];

    vector<vector<int>> adj(n + 1);
    for (int _ = 0; _ < n - 1; ++_) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<long long> dp(n + 1, 0);
    long long ans = LLONG_MIN;

    function<void(int, int)> dfs = [&](int u, int parent) {
        dp[u] = val[u];
        for (int v : adj[u]) {
            if (v == parent) continue;
            dfs(v, u);
            if (dp[v] > 0) dp[u] += dp[v];
        }
        ans = max(ans, dp[u]);
    };

    dfs(1, -1);
    cout << ans << '\n';
    return 0;
}

NOI1999 Optimal Connected Subset

Tree structure implicitly formed by Manhattan adjacency between grid points (dx + dy = 1). Apply same subtree-sum idea after constructing graph.

JSOI2016 Best Group (Ratio Optimization on Tree)

Binary search on ratio R = Σcost / Σvalue ⇒ check feasibility of Σ(cost − R·value) ≥ 0.

Tree knapsack DP: dp[u][k] = max posible sum in subtree of u selecting exactly k nodes.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int want, n;
    cin >> want >> n;
    want++;  // Include leader node

    vector<double> cost(n + 1), value(n + 1);
    vector<vector<int>> children(n + 1);

    for (int i = 1; i <= n; ++i) {
        cin >> cost[i] >> value[i];
        int p;
        cin >> p;
        children[p].push_back(i);
    }

    vector<vector<double>> dp(n + 1, vector<double>(want + 1, -1e18));
    vector<int> sz(n + 1, 1);

    function<void(int)> dfs = [&](int u) {
        dp[u][0] = 0;
        dp[u][1] = value[u];

        for (int v : children[u]) {
            dfs(v);
            for (int i = min(want, sz[u]); i >= 1; --i) {
                for (int j = 1; j <= sz[v] && i + j <= want; ++j) {
                    dp[u][i + j] = max(dp[u][i + j], dp[u][i] + dp[v][j]);
                }
            }
            sz[u] += sz[v];
        }

        // Ensure validity—only feasible when including u
        for (int i = 0; i <= want; ++i) dp[u][i] -= cost[u];
    };

    double lo = 0, hi = 10000;
    auto check = [&](double mid) -> bool {
        for (int u = 0; u <= n; ++u) fill(dp[u].begin(), dp[u].end(), -1e18);
        for (int i = 1; i <= n; ++i) dp[i][1] = value[i] - mid * cost[i];
        sz.assign(n + 1, 1);
        dfs(0);  // virtual root connects all
        return dp[0][want] >= 0;
    };

    while (hi - lo > 1e-4) {
        double mid = (lo + hi) / 2;
        if (check(mid)) lo = mid;
        else hi = mid;
    }

    cout << fixed << setprecision(3) << lo << '\n';
    return 0;
}

Bitmask DP

Cheece Eating (Traveling Salesman on Points)

Minimize path length starting from origin visiting all nodes once.

State: dp[i][mask] = shortest path ending at point i having visited set indicated by mask.

Precompute Euclidean distances between points, then iterate over masks in increasing order.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<double> x(n + 1), y(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> y[i];
    }
    x[0] = y[0] = 0;  // source at origin

    vector<vector<double>> dist(n + 1, vector<double>(n + 1));
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            double dx = x[i] - x[j], dy = y[i] - y[j];
            dist[i][j] = sqrt(dx * dx + dy * dy);
        }
    }

    int totalMask = 1 << n;
    vector<vector<double>> dp(n + 1, vector<double>(totalMask, 1e9));
    for (int i = 1; i <= n; ++i) dp[i][1 << (i - 1)] = dist[0][i];

    for (int mask = 1; mask < totalMask; ++mask) {
        for (int u = 1; u <= n; ++u) {
            if (!(mask & (1 << (u - 1)))) continue;
            for (int v = 1; v <= n; ++v) {
                if (u == v || !(mask & (1 << (v - 1)))) continue;
                dp[u][mask] = min(dp[u][mask], dp[v][mask ^ (1 << (u - 1))] + dist[v][u]);
            }
        }
    }

    double ans = 1e9;
    for (int i = 1; i <= n; ++i) {
        ans = min(ans, dp[i][totalMask - 1]);
    }
    cout << fixed << setprecision(2) << ans << '\n';
    return 0;
}

Mondriaan's Dream — Tiling with Dominoes

Classical problem: count ways to tile R×C grid with 2×1 dominoes.

Uses DP per row with states encoding轮廓 of filled cells as bitmask; transitions based on valid placements.

DP state: dp[row][mask] = number of completions given current row's occupancy pattern.

Transitions precomputed via DFS or BFS.