DP

Reusable dynamic-programming routines and common sequence problems.

Headers

Header	Summary
knapsack.hpp	Return best 0/1-knapsack values for every capacity through L. Items are grouped by equal weight and their values are sorted. Prefix sums inside a group form a concave sequence, so each residue class of capacities is updated by one concave max-plus convolution instead of per-item DP.
longest_common_subsequence.hpp	Return matched index pairs for one longest common subsequence in O(nm) time and memory.
longest_increasing_subsequence.hpp	Compute indices of a longest strictly increasing subsequence.