api: YAML JSON TOON Database
version: 1.0.0
format: toon
dataset:
  id: 2374
  slug: dynamic-programming-patterns
  title: Dynamic Programming Patterns
  description: Classic problems solved with dynamic programming.
  summary: "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_when[2]: "You need a canonical problem for a DP pattern such as a 1D, 2D or interval recurrence.",You are practicing recognizing overlapping subproblems.
  caveats[2]: 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.
  related[4]: greedy-algorithms,backtracking-algorithms,string-algorithms,complexity-classes
  entry_count: 15
  fields[2]{section,field,type,example}:
    data,problem,string,Fibonacci
    data,description,string,Compute nth Fibonacci using memoization or tabu…
  category: Algorithms
  category_slug: algorithms
  tags: "algorithms,dynamic-programming,optimization"
  view_count: 43
  created_at: 1792832553
  updated_at: 1792832553
data[15]{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.