Recognize the evidence, then choose the approach
Picture
A problem rarely announces its useful structure. Translate its story into a state, legal transitions, an objective, and constraints. Then ask what justifies avoiding work. The goal is to generate and defend an approach, and to notice when a small rule change removes its justification.
Predict
“A robot moves on a grid.” Which algorithm is that? What missing information prevents an honest answer?
Reveal the reasoning
You need the objective, legal moves, move costs, revisit rules, resource limits, and input size. The same grid can support BFS, Dijkstra, backtracking, DP, or a combination.
Go deeper: use contrasts to test recognition
| Evidence in the problem | Candidate idea | What must still be justified |
|---|---|---|
| Fewest equal-cost moves | BFS | State sufficiency and finite reachable search |
| Cheapest nonnegative-cost route | Dijkstra | Weight restriction and correct relaxation |
| All valid constructions | Backtracking | Completeness, no unwanted duplicates, feasible output size |
| Repeated equivalent remaining questions | DP | Sufficient state, recurrence, dependency order |
| Independent child subproblems | Tree aggregation or tree DP | Boundary information and no ignored cross-branch constraints |
| Repeated prefix queries | Trie | Query workload and output/memory costs |
| Repeated merges and undirected connectivity checks | Disjoint set | No unsupported deletions or path-output requirement |
| A monotone feasibility boundary | Binary search | Correct predicate and search bounds |
| A local choice supported by an exchange or other safety proof | Greedy | Proof assumptions hold for this objective |
This table generates candidates; it is not an automatic classifier. A DAG shortest-path algorithm can handle negative edges without Dijkstra. A tiny problem may be best served by exhaustive search. A tree problem can combine DFS and DP.
Work through a new problem in this order: restate what makes outputs distinct; solve a tiny instance manually; propose sufficient state; write the simplest complete search or recurrence; find repeated work or a safe elimination rule; count cost; attack the proposal with a changed assumption.
When you fail, name the failed step rather than “I am bad at DP.” Did you omit a resource? Confuse existence with enumeration? Read the wrong table layer? Assume a greedy exchange preserved value when it only preserved count? Each has a specific repair.
Analogy limit: recognizing a pattern is not matching a story’s nouns to a memorized template. Valid approaches depend on properties that may be hidden behind different stories.
Change one rule
Count right/down grid routes, then change the task to finding the fewest four-direction moves while removing at most one wall. What happens to the state and evaluation strategy?
Check the variation
Use (row,col,removals_left) because resources affect future moves. Equal move cost suggests BFS over that expanded state graph. Four-direction movement removes the earlier acyclic row/column recurrence. The same three-coordinate idea can belong to BFS rather than DP.
Connect
Take mixed practice without opening its answers. Then choose a build project. Revisit state, DP, or counterexamples whenever a justification fails.