Problem Archetypes

Attack the cell count, not the memory: quadratic time bites before space does. Trim the shared prefix and suffix, compare coarser units such as fingerprinted lines, and if only k edits matter, fill just the band where |i-j| <= k, which is O(n*k).

Only when something else will query the table. Both methods cost O(n^2) time for one longest symmetric run, but the table also costs O(n^2) memory. It pays off when an enclosing computation asks "is i..j symmetric?" many times, or when you need counts over all intervals.

The table loses when the capacity limit is enormous and the item count is not: 30 items and a billion-unit limit cost tens of billions of updates and gigabytes, while halved subset enumeration takes about a million operations.

The tails array holds at position k the smallest value that can end an increasing subsequence of length k+1. Its final length is the answer, but its contents are usually not a real subsequence of the input.

Subset DP's ceiling is exponential memory, so no tuning reaches 35 stops — the method must change. The real decision is what the last few percent of route quality is worth against a planner the team can operate and maintain.

Abandon it when planning cost stops buying execution savings: when quadratic memory or cubic time breaks the per-request budget, or when the size estimates feeding the cost function are so uncertain that the exact optimum is optimal only for a fiction.

Rerooting answers every node in two linear passes instead of one traversal per node, turning quadratic work into linear. Take it when the measured input size and recompute frequency actually miss the latency budget; below a few thousand nodes the simpler per-root loop usually wins and is far easier to keep correct.