Dynamic Programming Questions

Approach: Use classic SOS DP (subset DP over bits). Iterate bits i=0..n-1 and for every mask S, if bit i is set add dp[S ^ (1<<i)] to dp[S]. This accumulates contributions from all T ⊆ S in O(n*2^n). You can also do the inverse (to get f from g) by subtracting instead of adding.

#include <bits/stdc++.h>
using namespace std;
// Compute g[S] = sum_{T subset S} f[T] for all S (0..2^n-1)
vector<long long> sos_dp(vector<long long> f, int n) {
    int N = 1<<n;
    vector<long long> dp = f; // dp[S] will become g[S]
    for (int bit = 0; bit < n; ++bit) {
        for (int mask = 0; mask < N; ++mask) {
            if (mask & (1<<bit)) {
                dp[mask] += dp[mask ^ (1<<bit)];
            }
        }
    }
    return dp;
}

// Inverse transform: recover f from g
vector<long long> inverse_sos(vector<long long> g, int n) {
    int N = 1<<n;
    vector<long long> dp = g;
    for (int bit = 0; bit < n; ++bit) {
        for (int mask = 0; mask < N; ++mask) {
            if (mask & (1<<bit)) {
                dp[mask] -= dp[mask ^ (1<<bit)];
            }
        }
    }
    return dp;
}

int main(){
    int n = 3;
    vector<long long> f = {1,2,3,4,5,6,7,8}; // size 2^n
    auto g = sos_dp(f,n);
    for (auto x: g) cout<<x<<' '; // prints sums over subsets
    cout<<"\n";
}

Key points:

• Time: O(n * 2^n). Space: O(2^n).
• Works in-place; use 64-bit or modular arithmetic as needed.
• Edge cases: n=0 (N=1), large n (memory ~2^n), watch overflow.
  Practical use cases:
• Speeding up bitmask DP: precompute sums over subsets to answer queries like "sum of values for all submasks" in O(1) per query.
• Fast convolution-like operations (subset convolution, zeta transform) for counting subsets, DP over subsets of features, influence propagation in hypergraphs.
• Common in combinatorics, inclusion–exclusion transforms, and optimizing transitions in DP on bitmasks (e.g., TSP variants, partitioning, coverage).

Approach: compute winning positions with DP using Sprague–Grundy (SG) theory. For single pile, a position is winning iff its SG value ≠ 0. Moves allowed: remove {1,3,4}. For a single pile we can compute SG[n] = mex({SG[n-1], SG[n-3], SG[n-4]}), treating out-of-range moves as absent. O(N) time, O(N) space. For multiple piles, compute SG for each pile size and XOR (nim-sum) them; first player wins iff total_xor ≠ 0.

def winner_single(N):
    # returns True if first player wins with optimal play
    moves = [1,3,4]
    SG = [0]*(N+1)
    for n in range(1, N+1):
        reachable = set()
        for m in moves:
            if n-m >= 0:
                reachable.add(SG[n-m])
        # mex: smallest non-negative integer not in reachable
        mex = 0
        while mex in reachable:
            mex += 1
        SG[n] = mex
    return SG[N] != 0, SG  # boolean win, and table for inspection

def winner_multiple(piles):
    # piles: list of pile sizes
    maxN = max(piles) if piles else 0
    _, SG = winner_single(maxN)
    xor = 0
    for p in piles:
        xor ^= SG[p]
    return xor != 0  # True if first player wins

Key points:

• SG reduces impartial games to Nim piles; SG=0 means losing (P-position).
• Time: O(N) to build SG up to N; space O(N).
• For multiple piles, compute SG per pile size and XOR: nim-sum nonzero => N-position (first wins).
  Edge cases:
• N=0 => losing.
• Large N: if many queries, precompute once up to max required.
  Alternative: for this small move set you can detect periodicity in SG sequence to answer for huge N after finding cycle.

To compute DTW in O(n*m) and reconstruct the optimal warping path, we use dynamic programming building a cost matrix and backpointers. Below is a clear Python implementation with comments, followed by key points, complexity, pruning (Sakoe–Chiba), edge cases, and how DTW helps in ML pipelines.

import numpy as np

def dtw(a, b, dist=lambda x,y: abs(x-y)):
    """
    Compute full DTW cost matrix and optimal path between 1-D sequences a and b.
    Returns (cost, cost_matrix, path) where path is list of (i,j) from start->end.
    """
    n, m = len(a), len(b)
    # large value
    INF = float('inf')
    D = np.full((n+1, m+1), INF)
    D[0,0] = 0.0

    # accumulate costs
    for i in range(1, n+1):
        for j in range(1, m+1):
            c = dist(a[i-1], b[j-1])
            D[i,j] = c + min(D[i-1,j], D[i,j-1], D[i-1,j-1])

    cost = D[n,m]

    # backtrack path
    i, j = n, m
    path = []
    while i>0 or j>0:
        path.append((i-1, j-1))
        choices = [(D[i-1,j-1], i-1, j-1), (D[i-1,j], i-1, j), (D[i,j-1], i, j-1)]
        best, i, j = min(choices, key=lambda x: x[0])
    path.reverse()
    return cost, D[1:,1:], path

Key points:

• Time: O(nm); Space: O(nm) for full matrix (can reduce to O(min(n,m)) for cost only).
• Path reconstructed via backtracking from (n,m) to (0,0) using minimal predecessor.
• Sakoe–Chiba band: restrict j to [i-w, i+w] (window w) in loops to prune; complexity becomes O(n*w).
• Edge cases: empty sequences (define cost 0 or INF), multivariate series (use vector distance like Euclidean), large sequences (use windowing or lower-bounds like LB_Keogh).

DTW in ML pipelines:

• Use DTW distance as similarity for k-NN, clustering, or to compute features (DTW distance to prototypes).
• Preprocessing: compute DTW-based barycenters (DBA) to create robust centroids; use lower-bounds to filter candidates for speed; normalize series (z-score) before DTW.
• Combine with dimensionality reduction (SAX, PAA) or windowing to scale to large datasets.

Brief idea: when the optimal split index opt[i] = argmin_j DP[k-1][j] + C[j+1..i] is monotone (opt[i] ≤ opt[i+1]), you can compute a whole DP row by divide-and-conquer: recursively compute DP values for a segment [L..R] while restricting the search for opt[mid] to [optL..optR]. This reduces total work because each DP[mid] only scans a small, shrinking range.

Algorithm (recursive D&C):

• Compute dpRow[i] for i in [1..n].
• Recurse solve(L,R,optL,optR):
  • mid = (L+R)//2
  • best = argmin_{j in [optL..min(mid-1,optR)]} DPprev[j] + C[j+1..mid]
  • dpRow[mid] = value at best; optMid = best
  • solve(L, mid-1, optL, optMid)
  • solve(mid+1, R, optMid, optR)

Correctness sketch:

• Invariant: true optimal opt for any i in [L..R] lies within [optL..optR]. Base call uses [1..n] and [0..n-1].
• Monotonicity ensures when you find optMid, no optimal index for left half is > optMid and no optimal for right half is < optMid, so recursive bounds are safe. By induction all dp values computed are optimal.

Complexity:

• Each level of recursion examines at most O(n) candidate j's in total across that level; there are O(log n) levels → O(n log n) evaluations of the cost term.
• If cost C[j+1..i] can be computed in O(1) (with prefix summaries) the runtime is O(n log n) per DP row.
• In some cases (e.g., when you can amortize scanning so each j is considered O(1) times across recursion) complexity becomes O(n) (tight when combined with additional structure or using SMAWK for totally monotone matrices).

Example where monotonicity holds: DP for partitioning 1D points into k segments minimizing squared error (k-means 1D). Let A[1..n] be points, prefix sums S and S2. Cost of segment [l..r]:
C[l..r] = sum_{t=l..r} (A[t] - mean_{l..r})^2 = S2[r]-S2[l-1] - (S[r]-S[l-1])^2/(r-l+1)
This cost satisfies quadrangle inequality and yields monotone opt indices. Use the D&C algorithm above; precompute S,S2 to get C in O(1). For k up to K, repeat building each row with D&C; total O(K n log n) (or O(K n) with stronger guarantees).

Small pseudo-code (Python-like):

def compute_dp_row(DPprev, n):
    dp = [inf]*(n+1)
    def solve(L,R,optL,optR):
        if L>R: return
        mid=(L+R)//2
        best,optv = -1,INF
        for j in range(optL, min(mid-1,optR)+1):
            val = DPprev[j] + cost(j+1, mid)  # O(1)
            if val < optv:
                optv, best = val, j
        dp[mid]=optv
        solve(L, mid-1, optL, best)
        solve(mid+1, R, best, optR)
    solve(1,n,0,n-1)
    return dp

Takeaway: D&C DP reduces the search for each dp[i] to a small interval using monotonicity; with O(1) cost queries it runs in O(n log n) per row and is widely used for k-partition and clustering DP problems.

Hirschberg’s algorithm computes the LCS string in O(n*m) time but only O(min(n,m)) extra space by using divide-and-conquer plus linear-space DP passes that compute LCS lengths (not the full table). Idea: for strings A (length n) and B (length m) compute midpoint of A, run forward DP on A[0:mid] vs B to get lengths L1[j], run backward DP on reversed A[mid:] and reversed B to get lengths L2[j]; pick split point k in B maximizing L1[k]+L2[m-k]; that k gives a partition of B. Recurse on (A[0:mid], B[0:k]) and (A[mid:], B[k:]). Base cases when one side length is 0 or 1 produce direct LCS.

Approach and code (Python):

def lcs_hirschberg(A, B):
    # returns LCS string
    def lcs_len_row(X, Y):
        # computes last row of DP for LCS(len) between X and all prefixes of Y
        # uses O(len(Y)) space
        prev = [0]*(len(Y)+1)
        for x in X:
            cur = [0]*(len(Y)+1)
            for j, y in enumerate(Y,1):
                if x == y:
                    cur[j] = prev[j-1] + 1
                else:
                    cur[j] = cur[j-1] if cur[j-1] >= prev[j] else prev[j]
            prev = cur
        return prev

    def recurse(X, Y):
        n, m = len(X), len(Y)
        if n == 0 or m == 0:
            return ""
        if n == 1:
            # direct check if X[0] in Y
            return X[0] if X[0] in Y else ""
        mid = n // 2
        L1 = lcs_len_row(X[:mid], Y)                      # forward
        L2 = lcs_len_row(X[mid:][::-1], Y[::-1])[::-1]   # backward reversed and reversed back
        # choose split k maximizing L1[k]+L2[k]
        best_k = max(range(len(Y)+1), key=lambda k: L1[k] + L2[k])
        return recurse(X[:mid], Y[:best_k]) + recurse(X[mid:], Y[best_k:])
    return recurse(A, B)

Key points:

• lcs_len_row computes DP row-by-row; each row needs O(m) memory.
• For backward pass reverse both substrings; reverse result to align indices.
• Recursion depth O(log n) if splitting balanced; in worst-case O(n) but each level processes disjoint subproblems of total O(n*m) work across recursion.

Complexity proof:

• Time: Each recursion level computes two linear-space DP passes across A and B segments. Summing work across recursion yields T(n,m)=T(n1,m1)+T(n2,m2)+O(nm) splitting cost amortizes to O(nm).
• Space: lcs_len_row uses O(m) (choose m = min(len(A),len(B)) by swapping). Recursion uses stack O(min(n,m)) in practice O(n) worst if skewed, but you can make recursion iterative or tail-optimize. So extra space O(min(n,m)) for arrays; call stack adds O(log n) average.

Edge cases and practical limits:

• Very large strings (millions): time O(n*m) becomes infeasible. Use heuristics: suffix/rolling-hash, bitset-based LCS (bit-parallel) if alphabet small, or approximate LCS (diff algorithms). For memory, ensure you always treat the shorter string as Y so arrays are minimal. For extreme sizes use external memory or streaming approximations.
• If recursion depth is a concern, replace recursion with an explicit stack.
• Characters vs bytes: consider encoding and large alphabets affecting bit-parallel methods.

This implementation returns the actual LCS string and demonstrates forward/backward linear-space passes, midpoint splitting, and overall complexities.