YUNOVA · Data Structures & Algorithms
Module 11: Advanced dynamic programming
DP on grids
Key points
- Grid DP stores the answer for each cell, built from neighbouring cells.
- Unique paths: dp[i][j] = dp[i-1][j] + dp[i][j-1].
- Fill the table row by row so needed cells are already computed.
Longest increasing subsequence
Key points
- The O(n²) LIS uses dp[i] = longest increasing subsequence ending at i.
- Patience sorting with binary search finds LIS length in O(n log n).
- A subsequence keeps the original order but need not be contiguous.
DP on trees
Key points
- Tree DP computes each node's answer from its children's answers using DFS.
- Many problems keep two states per node, such as taken and not taken.
- Rerooting finds the answer for every node as the root in O(n).
Bitmask DP
Key points
- A bitmask stores which items of a small set are chosen as bits of an integer.
- Bitmask DP suits n up to about 20, since there are 2^n states.
- Travelling salesman uses dp[mask][last], solved in O(2^n · n²).
Matrix chain multiplication and interval DP
Key points
- Interval DP solves dp[i][j] for a range by trying every split point k.
- Matrix chain finds the multiplication order with the fewest scalar multiplications.
- Fill the table by increasing interval length.