Problem Modeling (Translating Problems into Graphs & DP)
Problem Modeling maps real-world or word-problem scenarios onto canonical structures—graphs, DAGs, flow networks, intervals, or state machines—so standard algorithms solve them immediately.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Problem Modeling
The hardest step in competitive programming and system design is rarely coding the algorithm—it is recognizing what model hides beneath the story:
| Problem Signal | Canonical Model | Go-To Algorithm |
| :--- | :--- | :--- |
| "Minimum steps / moves / transformations" | Unweighted State Graph | BFS |
| "Prerequisites / ordering / dependencies" | Directed Acyclic Graph (DAG) | Topological Sort |
| "Connect everything with minimum cost" | Undirected Weighted Graph | Kruskal / Prim |
| "Minimize the maximum / maximize the minimum" | Monotonic Feasibility Predicate | Binary Search on Answer |
| "Pair left items with right items / cut dependencies" | Flow Network | Dinic's Max Flow |
---
Example: Modeling Word Ladder as Shortest Path in a Graph
Each word is a vertex; two words differing by 1 character share an undirected edge. Shortest transformation length = BFS distance!
<details>
<summary>Show C++ Example</summary>
#include <iostream>
#include <queue>
#include <string>
#include <unordered_set>
#include <vector>
int wordLadder(const std::string& begin, const std::string& end, const std::vector<std::string>& dict) {
std::unordered_set<std::string> words(dict.begin(), dict.end());
if (!words.count(end)) return 0;
std::queue<std::pair<std::string, int>> q;
q.push({begin, 1});
words.erase(begin);
while (!q.empty()) {
auto [cur, dist] = q.front(); q.pop();
if (cur == end) return dist;
for (size_t i = 0; i < cur.size(); ++i) {
char orig = cur[i];
for (char c = 'a'; c <= 'z'; ++c) {
cur[i] = c;
if (words.erase(cur)) q.push({cur, dist + 1});
}
cur[i] = orig;
}
}
return 0;
}
int main() {
std::cout << wordLadder("hit", "cog", {"hot", "dot", "dog", "lot", "log", "cog"}) << "\n"; // 5
return 0;
}
</details>
---