Dynamic programming

Optimization problems solved by tabulated recurrences: knapsack variants, subset sum, rod cutting, matrix-chain ordering, optimal binary search trees, longest common and longest increasing subsequences (including patience sorting) and maximum subarray (Kadane and divide-and-conquer); string edit distance goes to String algorithms.

• Longest common subsequence
• Longest increasing subsequence
• Matrix chain multiplication
• Maximum subarray problem
• Multiple-choice knapsack problem
• Optimal binary search tree
• Rod cutting
• Subset sum
• Zero-one knapsack problem

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.