Dynamic Programming Patterns
Classic problems solved with dynamic programming.
Classic dynamic-programming problems: Fibonacci, 0/1 knapsack, longest common subsequence, longest increasing subsequence, coin change, matrix chain multiplication, edit distance and maximum subarray, extended with rod cutting, longest palindromic subsequence, partition, house robber, word break, unique paths and egg dropping.
Use it when
- You need a canonical problem for a DP pattern such as a 1D, 2D or interval recurrence.
- You are practicing recognizing overlapping subproblems.
Watch out for
- DP needs optimal substructure and overlapping subproblems; check both before applying it.
- Table size can dominate memory; space optimizations often keep only the previous row.
The data
15 rows
| Problem | Description |
|---|---|
| Fibonacci | Compute nth Fibonacci using memoization or tabulation. |
| 0/1 Knapsack | Select items to maximize value without exceeding capacity. |
| Longest Common Subsequence | Find longest subsequence present in two sequences. |
| Longest Increasing Subsequence | Find longest strictly increasing subsequence. |
| Coin Change | Minimum coins needed to make a target amount. |
| Matrix Chain Multiplication | Optimal parenthesization for multiplying matrices. |
| Edit Distance | Minimum operations to convert one string to another. |
| Maximum Subarray | Contiguous subarray with the largest sum. |
| Rod Cutting | Cut a rod into pieces to maximize total price given a price for each length. |
| Longest Palindromic Subsequence | Find the longest subsequence of a string that reads the same in both directions. |
| Partition Problem | Decide whether a set can be split into two subsets with equal sums. |
| House Robber | Maximize the loot from a row of houses without taking two adjacent houses. |
| Word Break | Decide whether a string can be segmented into words from a dictionary. |
| Unique Paths | Count the paths from the top-left to the bottom-right of a grid moving only right or down. |
| Egg Dropping | Find the minimum number of trials needed to determine the highest safe floor with a given number of eggs. |
Fields
The shape of this dataset, read from the data itself: every column, its type and a real value. Agents can use this to plan a query without fetching the whole document.
| Section | Field | Type | Example |
|---|---|---|---|
| data | problem | string | Fibonacci |
| data | description | string | Compute nth Fibonacci using memoization or tabu… |
Fetch the same bytes
The static files contain the same reference rows as the API, with no API rate limit. Live metadata, such as view counts, may differ. Use the API for content negotiation; use the static files for a cacheable snapshot.
curl "https://yjtoon.com/api/dataset/dynamic-programming-patterns?format=toon"
const res = await fetch( "https://yjtoon.com/static-data/dataset/dynamic-programming-patterns.toon" ); const toon = await res.text();
Rate limit: 120 requests per minute per IP, no key and no signup. API reference →