You Have Seen DP. But Can You Spot It?

You know how to define states, write transitions, and handle base cases. You have solved Coin Change, grid paths, and maybe even some string DP.

But hand you a NEW problem --- one you have never seen --- and how do you decide if it is DP, greedy, or backtracking? How do you know WHICH kind of DP?

Most people rely on keyword heuristics: “minimize” means DP, “generate all” means backtracking. These heuristics fail on real problems. Let us find out if yours work.

Pattern or Panic?

Four problems. No hints. No framework. Just your gut.

Classify each one, see what happens when you are wrong, then build the tool that makes gut instinct unnecessary.

1 / 4
Given coins 134, find the minimum number of coins that make amount 6.

Classify this problem:

The Shape Tells the Story

You discovered it yourself: the state SHAPE reveals the family.

  • 1D indexed by a value (amount, capacity) --- Knapsack family
  • 2D indexed by coordinates (row, col) --- Grid DP
  • 2D indexed by range endpoints (i, j where j > i) --- Interval DP
  • Per-node in a tree --- Tree DP

Next time you face a new problem, do not ask “is this DP?” Ask: “what is the state?” The shape will answer everything else.