DSA: Dynamic Programming Advanced
Master LIS variants, bitmask DP, tree DP, palindrome partitioning, and TSP.
Longest Increasing Subsequence (LIS)
Find the length of the longest strictly increasing subsequence in an array. Two approaches exist: O(n²) DP and O(n log n) using binary search with a patience-sort tails array.
LIS
O(n²): dp[i] = length of LIS ending at index i. O(n log n): maintain smallest tail for each LIS length.
- O(n²) recurrence: dp[i] = max(dp[j] + 1) for all j < i where arr[j] < arr[i]
- O(n log n): tails[] where tails[k] = smallest tail of LIS of length k+1
- Binary search finds the correct position to update in tails[]
- len(tails) at the end = LIS length; tails itself is NOT the LIS
LIS (O(n log n))
C++Maintain tails array: binary search to find and replace the ceiling element.
Longest Bitonic Subsequence
A bitonic subsequence first increases then decreases. Compute LIS from the left and LDS from the right, then combine at each index.
Longest Bitonic Subsequence
LBS[i] = LIS ending at i + LDS starting at i - 1 (index i counted once in both).
- lis[i]: LIS length ending at index i (left to right)
- lds[i]: LDS length starting at index i (right to left, same as LIS on reversed array)
- LBS[i] = lis[i] + lds[i] - 1
- Answer: max over all i of LBS[i]
- Indices where lis[i] == 1 or lds[i] == 1 give only increasing or only decreasing: still valid
Longest Bitonic Subsequence
C++Combine LIS from left and LDS from right at each index.
Maximum Sum Increasing Subsequence
Find the increasing subsequence with the maximum sum (not necessarily the longest). Uses the LIS O(n²) structure but tracks sum instead of length.
Maximum Sum Increasing Subsequence
msis[i] = max sum of increasing subsequence ending at index i.
- Initialize msis[i] = arr[i] (subsequence of just itself)
- Recurrence: msis[i] = arr[i] + max(msis[j]) for j < i where arr[j] < arr[i]
- Answer: max of all msis[i]
- Same structure as LIS O(n²), replace length with sum
Maximum Sum Increasing Subsequence
C++Track sum instead of count; same O(n²) recurrence as LIS.
Russian Doll Envelopes
Envelope A fits inside B if both dimensions are strictly smaller. Find the maximum number of envelopes that can be nested. Reduces to LIS after a careful sort.
Russian Doll Envelopes
Sort by width ascending, height descending. Then run LIS on heights only.
- Sort ascending by width; for equal widths sort descending by height
- Descending height for equal widths prevents picking two envelopes of same width
- After sort: LIS on heights gives the answer
- Time: O(n log n) with optimal LIS; Space: O(n)
Russian Doll Envelopes
C++Sort trick prevents double-counting same width; then LIS on heights.
DP on Trees: Diameter
The diameter of a tree is the longest path between any two nodes. At each node, combine the two deepest subtree depths to get the path through that node, and propagate the max upward.
Tree Diameter (DP)
At each node: candidate diameter = depth1 + depth2 (two longest child paths). Return depth1 + 1 to parent.
- DFS returns the maximum depth of the subtree rooted at each node
- At each node: sort children depths, add top two for local diameter candidate
- Global answer = max local candidate seen across all nodes
- Time: O(n), Space: O(n) recursion stack
Tree Diameter
C++DFS returning depth; track top-two children to find the longest through-path.
Palindrome Partitioning (Minimum Cuts)
Find the minimum number of cuts needed to partition a string so every part is a palindrome. Precompute a palindrome table, then run a 1D DP for minimum cuts.
Palindrome Partitioning
dp[i] = minimum cuts for s[0..i]. Try every j from 0 to i; if s[j..i] is a palindrome, dp[i] = min(dp[i], dp[j-1] + 1).
- Precompute isPalin[i][j] in O(n²) using interval DP
- dp[i] = 0 if s[0..i] is already a palindrome
- dp[i] = min over j in [1..i] of (dp[j-1] + 1) where isPalin[j][i] is true
- Time: O(n²), Space: O(n²) for palindrome table
Palindrome Partitioning Minimum Cuts
C++Precompute palindrome table then apply 1D cut DP.
Traveling Salesman Problem (Bitmask DP)
Visit every city exactly once and return to the start with minimum total cost. Bitmask DP encodes the set of visited cities as an integer, giving O(2^n * n²) time instead of O(n!).
TSP Bitmask DP
dp[mask][i] = min cost to reach city i having visited exactly the cities in mask.
- mask is a bitmask: bit j set means city j has been visited
- Transition: dp[mask | (1<
- Answer: min over all i of dp[(1<
- Start: dp[1][0] = 0 (at city 0, only city 0 visited)
- Time: O(2^n * n²), feasible for n up to ~20
TSP with Bitmask DP
C++Encode visited city set as bitmask; transition by adding one unvisited city.
Advanced DP Problem Map
Advanced DP problems group by the state space dimension and structure used.
| Problem | DP State | Time | Key Insight |
|---|---|---|---|
| LIS O(n²) | dp[i]: LIS ending at i | O(n²) | For each i check all j < i |
| LIS O(n log n) | tails[k]: smallest tail | O(n log n) | Binary search on tails array |
| Bitonic Subseq | lis[i] + lds[i] | O(n²) | LIS left + LDS right at each i |
| Max Sum IS | msis[i]: max sum at i | O(n²) | Same as LIS, track sum |
| Russian Doll | LIS on heights | O(n log n) | Sort trick prevents same-width nesting |
| Tree Diameter | depth per node | O(n) | Top-two child depths at each node |
| Palindrome Cuts | dp[i]: min cuts | O(n²) | Precompute isPalin table |
| TSP Bitmask | dp[mask][i] | O(2^n * n²) | Bitmask encodes visited set |
Knowledge Check
1. What is the time complexity of LIS using binary search (patience sorting)?
2. The Longest Bitonic Subsequence at index i equals:
3. Russian Doll Envelopes reduces to LIS after sorting. How should envelopes be sorted?
4. In Bitmask DP for Traveling Salesman, dp[mask][i] represents:
5. Palindrome Partitioning (minimum cuts) dp[i] represents:
6. In DP on trees (diameter), why must the two longest child paths be combined at a node?
7. Maximum Sum Increasing Subsequence recurrence is:
8. The Bitmask TSP has how many states?