api: YAML JSON TOON Database
version: 1.0.0
format: json
dataset:
  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:
    - You need a canonical problem for a DP pattern such as a 1D, 2D or interval recurrence.
    - You are practicing recognizing overlapping subproblems.
  caveats:
    - 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:
    - greedy-algorithms
    - backtracking-algorithms
    - string-algorithms
    - complexity-classes
  category: Algorithms
  category_slug: algorithms
  tags: algorithms,dynamic-programming,optimization
  view_count: 0
  entry_count: 15
  fields:
    - section: data
      field: problem
      type: string
      example: Fibonacci
    - section: data
      field: description
      type: string
      example: Compute nth Fibonacci using memoization or tabu…
data:
  - problem: Fibonacci
    description: Compute nth Fibonacci using memoization or tabulation.
  - problem: 0/1 Knapsack
    description: Select items to maximize value without exceeding capacity.
  - problem: Longest Common Subsequence
    description: Find longest subsequence present in two sequences.
  - problem: Longest Increasing Subsequence
    description: Find longest strictly increasing subsequence.
  - problem: Coin Change
    description: Minimum coins needed to make a target amount.
  - problem: Matrix Chain Multiplication
    description: Optimal parenthesization for multiplying matrices.
  - problem: Edit Distance
    description: Minimum operations to convert one string to another.
  - problem: Maximum Subarray
    description: Contiguous subarray with the largest sum.
  - problem: Rod Cutting
    description: Cut a rod into pieces to maximize total price given a price for each length.
  - problem: Longest Palindromic Subsequence
    description: Find the longest subsequence of a string that reads the same in both directions.
  - problem: Partition Problem
    description: Decide whether a set can be split into two subsets with equal sums.
  - problem: House Robber
    description: Maximize the loot from a row of houses without taking two adjacent houses.
  - problem: Word Break
    description: Decide whether a string can be segmented into words from a dictionary.
  - problem: Unique Paths
    description: Count the paths from the top-left to the bottom-right of a grid moving only right or down.
  - problem: Egg Dropping
    description: Find the minimum number of trials needed to determine the highest safe floor with a given number of eggs.