Dynamic Programming Questions

The convex hull trick (CHT) maintains a set of lines y = m*x + b and answers queries min_y at given x. For arbitrary slopes or online (queries and insertions interleaved, slopes not monotonic) we use a Li Chao tree: a segment tree over x-coordinates where each node stores the line that is currently best on that node's interval; insertion swaps lines and pushes the loser down. This yields O(log C) per insert/query where C = coordinate range (or O(log N) if compressed).

C++ implementation (dynamic Li Chao over integer x in [X_MIN, X_MAX]):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<62);
struct Line { ll m,b; Line(ll _m=0,ll _b=INF):m(_m),b(_b){} ll eval(ll x) const { return m*x + b; } };
struct LiChao {
    struct Node { Line ln; Node *l=0,*r=0; Node(Line v=Line()):ln(v){} };
    Node* root=nullptr; ll L, R;
    LiChao(ll L_, ll R_):L(L_),R(R_){}
    void add_line(Line nw){ root = add_line(root, L, R, nw); }
    Node* add_line(Node* node, ll l, ll r, Line nw){
        if(!node) node = new Node(nw);
        Line lo = node->ln, hi = nw;
        ll mid = (l+r)>>1;
        if(lo.eval(mid) > hi.eval(mid)) swap(node->ln, nw), lo = node->ln, hi = nw;
        if(l==r) return node;
        if(lo.eval(l) > hi.eval(l)) node->l = add_line(node->l, l, mid, hi);
        else if(lo.eval(r) > hi.eval(r)) node->r = add_line(node->r, mid+1, r, hi);
        return node;
    }
    ll query(ll x){ return query(root, L, R, x); }
    ll query(Node* node, ll l, ll r, ll x){
        if(!node) return INF;
        ll res = node->ln.eval(x);
        if(l==r) return res;
        ll mid=(l+r)>>1;
        if(x<=mid) return min(res, query(node->l, l, mid, x));
        else return min(res, query(node->r, mid+1, r, x));
    }
};

Key points:

• Time: O(log C) per insert/query (C = x-range). If x compressed to M distinct x-values, use segment tree over indices -> O(log M).
• Space: O(#nodes) up to O(#lines * log C) in worst-case dynamic growth.
• Works online: insertions and queries interleaved, slopes arbitrary.

When to prefer Li Chao vs deque-based CHT:

• Use deque (or monotonic hull with binary search) when slopes are inserted in monotonic order and queries are monotonic (or arbitrary with binary search). That gives O(1) amortized insert and O(log N) or O(1) query depending on variant — faster and simpler.
• Use Li Chao when slopes are arbitrary, queries online or x-values not monotonic, or when coordinate compression still leaves arbitrary order. Li Chao handles these with guaranteed logarithmic bounds.

Edge cases:

• Large x-range -> compress coordinates first to reduce tree height.
• Use 128-bit if products m*x overflow 64-bit.
• Minimization vs maximization: flip signs accordingly.

This pattern is ideal to optimize DP like dp[i] = min_j (m_j * x_i + b_j) when lines correspond to previous states; insert line when j becomes available and query at x_i.

Approach: Precompute isPal[i][j] in O(n^2) using expanding/DP, then compute minCuts[i] = min cuts for s[:i+1] with DP: minCuts[i] = 0 if s[0..i] is palindrome else min(minCuts[j-1]+1 for j in 1..i if s[j..i] is palindrome). Reconstruct one partition by tracking prev cut positions.

def min_cut_and_partition(s):
    n = len(s)
    if n == 0: return 0, []
    # Precompute palindromes
    isPal = [[False]*n for _ in range(n)]
    for center in range(n):
        # odd
        l=r=center
        while l>=0 and r<n and s[l]==s[r]:
            isPal[l][r]=True; l-=1; r+=1
        # even
        l, r = center, center+1
        while l>=0 and r<n and s[l]==s[r]:
            isPal[l][r]=True; l-=1; r+=1

    # DP for min cuts and predecessor for reconstruction
    INF = n
    minCuts = [INF]*n
    prev = [-1]*n
    for i in range(n):
        if isPal[0][i]:
            minCuts[i]=0; prev[i]=-1
        else:
            for j in range(1, i+1):
                if isPal[j][i] and minCuts[j-1]+1 < minCuts[i]:
                    minCuts[i] = minCuts[j-1]+1
                    prev[i] = j-1

    # Reconstruct partition
    parts = []
    i = n-1
    while i >= 0:
        j = prev[i]
        start = 0 if j==-1 else j+1
        parts.append(s[start:i+1])
        i = j
    parts.reverse()
    return minCuts[n-1], parts

# Example:
# min_cut_and_partition("aab") -> (1, ["aa","b"])

Key points:

• Time: O(n^2) for palindrome table + O(n^2) for DP => O(n^2). Space: O(n^2) for isPal, O(n) for DP arrays.
• Edge cases: empty string, all characters same (cuts=0), length 1, long string up to 1000 (n^2 ~1e6 is OK).
• Optimizations: reduce memory by computing palindrome info on the fly or using boolean bitsets; early break when minCuts reaches 0 for prefix.
• This returns minimum cuts and one valid partition; to return all partitions would be exponential.

Overlapping subproblems: a problem has overlapping subproblems if the same subproblems are solved multiple times during a naïve recursive solution. Example where it holds: Fibonacci(n) computed recursively calls Fib(n-1) and Fib(n-2) repeatedly; memoization / bottom-up DP turns exponential recursion into O(n). Example where it doesn't hold: computing all permutations of n distinct items — each recursive branch generates unique subproblems (different sets used), so memoization gives little reuse.

Optimal substructure: a problem has optimal substructure if an optimal solution to the whole problem contains optimal solutions to its subproblems. Example where it holds: shortest-path in a weighted graph without negative cycles (Dijkstra/Bellman-Ford). Any shortest path from s to t that goes through v must have the subpath s→v be shortest. Example where it doesn't hold: the longest simple path problem in general graphs — a longest path that includes a subpath might force that subpath to be non-optimal locally because choosing the locally longest subpath could prevent feasible extension to a global optimum.

Why recognize these before using DP:

• DP relies on reusing subproblem results (overlapping subproblems) and combining optimal sub-solutions into a global optimum (optimal substructure). If either property is missing, DP is ineffective or incorrect: no reuse means no asymptotic gain; lack of optimal substructure means greedy/DP composition can produce wrong answers. Checking both guides correct algorithm choice (memoization, bottom-up DP, greedy, search, or specialized techniques).

Start by asking: does the problem satisfy the greedy/exchange property? Practically: try to (a) formalize a greedy rule, (b) attempt a proof by exchange (show any optimal solution can be transformed to the greedy solution without loss), and (c) falsify by small counterexamples or exhaustive search. If you can’t prove the exchange property, implement a brute-force/DP solver and test randomly against the greedy — if you find counterexamples, greedy is not sufficient.

Counterexample (natural greedy: "always pick highest-profit interval first"):

• I1 = [0,3], profit 9
• I2 = [3,6], profit 9
• I3 = [2,4], profit 17
• Penalty: if two chosen intervals overlap, subtract 10 for that overlapping pair.

Greedy picks I3 first (profit 17). I3 overlaps I1 and I2, so you cannot take them without paying penalty; best greedy total = 17. Optimal is pick I1 and I2 (no overlap between them) for total 9+9 = 18. Greedy fails.

DP formulation that correctly solves it (general, pairwise overlap penalty):
Sort intervals by start time or end time and index 0..n-1. Use DP with state (i, last) = best profit considering intervals from i..n-1 when the last-picked interval index is last (or last = -1 for none). Decision at i:

• Skip i: value = dp(i+1, last)
• Take i: value = profit[i] - penalty_if_overlap(last,i) + dp(i+1, i)
  Return dp(0, -1).

This is a straightforward recursion with memoization; it correctly accounts for pairwise penalties because each time you pick a new interval you immediately account for penalty with the previously chosen interval. If penalties interact with multiple earlier intervals (not just the last), the state must include all active chosen intervals — that can blow up; complexity depends on penalty structure. For pairwise penalties that only depend on overlap with previously chosen intervals generally you can keep last and still be correct if penalty only occurs between consecutive choices in time order; otherwise you need a more complex state or approximate/graph-based methods.

Example DP implementation (O(n^2) worst case):

# intervals = [(start,end,profit), ...] sorted by start
from functools import lru_cache

def overlap(a,b):
    return not (a[1] <= b[0] or b[1] <= a[0])

PENALTY = 10

@lru_cache(None)
def dp(i, last):  # last is index or -1
    if i == len(intervals):
        return 0
    # skip i
    best = dp(i+1, last)
    # take i, apply penalty if overlaps with last
    penalty = PENALTY if last != -1 and overlap(intervals[last], intervals[i]) else 0
    take = intervals[i][2] - penalty + dp(i+1, i)
    return max(best, take)

result = dp(0, -1)

Complexity: O(n^2) states (n choices for i × ~n for last) and O(1) transition, so O(n^2) time and O(n^2) memory. If penalties only depend on adjacency in sorted order this is tight and correct. If penalties are global pairwise for arbitrary overlaps, the problem becomes a quadratic 0-1 optimization (sum w_i x_i - sum p_{ij} x_i x_j) and may be NP-hard; in that case either restrict the penalty structure, use branch-and-bound, or apply approximations.

Takeaway:

• Test greedy by attempting an exchange proof and by running brute-force/DP comparisons on small random instances.
• Provide a DP whose state captures the necessary history (e.g., last chosen interval). If history needs to be richer, the DP may become exponential or the problem may be intrinsically hard.

To compute LIS length in O(n log n) we maintain an array tails where tails[len] = smallest possible tail value of an increasing subsequence of length len+1. For each x we binary-search the first tail >= x and replace it (or append if none). For reconstruction keep:

• tails_vals: values used for tails
• tails_idx: index in original array of the tail value
• prev: predecessor index for each element (to rebuild sequence)

Algorithm:

1. Iterate i over array a:

• find pos = lower_bound(tails_vals, a[i])
• set prev[i] = tails_idx[pos-1] if pos>0 else -1
• tails_vals[pos] = a[i], tails_idx[pos] = i

2. Track LIS length = size of tails_vals and last index = tails_idx[-1]
3. Reconstruct by following prev from last index backwards.

Python sketch:

from bisect import bisect_left

def lis_with_reconstruction(a):
    n = len(a)
    tails_vals = []
    tails_idx = []
    prev = [-1]*n

    for i, x in enumerate(a):
        pos = bisect_left(tails_vals, x)  # first >= x
        if pos == len(tails_vals):
            tails_vals.append(x)
            tails_idx.append(i)
        else:
            tails_vals[pos] = x
            tails_idx[pos] = i
        if pos > 0:
            prev[i] = tails_idx[pos-1]

    length = len(tails_vals)
    # reconstruct one LIS
    lis = []
    cur = tails_idx[-1] if tails_idx else -1
    while cur != -1:
        lis.append(a[cur])
        cur = prev[cur]
    lis.reverse()
    return length, lis

Key points:

• lower_bound ensures minimal tail for each length (greedy).
• prev links let you recover one valid LIS.
  Time: O(n log n) due to binary searches. Space: O(n) for arrays and pointers.
  Edge cases: empty input, duplicates (use <= vs < depending on strictly increasing vs non-decreasing). Alternative: patience piles visualization; for strict vs non-strict adjust bisect.