Concepts80
Category
Coin Change and Variants
Coin Change uses dynamic programming to find either the minimum number of coins to reach a target or the number of ways to reach it.
Dynamic Programming Fundamentals
Dynamic programming (DP) solves complex problems by breaking them into overlapping subproblems and using their optimal substructure.
DP State Design
Dynamic Programming (DP) state design is the art of choosing what information to remember so that optimal substructure can be reused efficiently.
Bipartite Matching - Hopcroft-Karp
Hopcroft–Karp computes maximum matching in a bipartite graph in O(E \sqrt{V}) time, which is asymptotically faster than repeated DFS (Kuhn's algorithm).
Bipartite Matching - Kuhn's Algorithm
Kuhn’s algorithm finds a maximum matching in a bipartite graph by repeatedly searching for augmenting paths using DFS.
König's Theorem
König's Theorem states that in any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.
Flow - Modeling Techniques
Many classic problems can be modeled as a maximum flow problem by building the right network and capacities.
Min-Cut Max-Flow Theorem
The Max-Flow Min-Cut Theorem says the maximum amount you can push from source to sink equals the minimum total capacity you must cut to disconnect them.
Maximum Flow - Dinic's Algorithm
Dinic's algorithm computes maximum flow by repeatedly building a level graph with BFS and sending a blocking flow using DFS.
Maximum Flow - Ford-Fulkerson
Ford–Fulkerson finds the maximum possible flow from a source to a sink by repeatedly pushing flow along an augmenting path in the residual graph.
LCA - Binary Lifting
Binary lifting precomputes 2^k ancestors for every node so we can jump upward in powers of two.
Strongly Connected Components
Strongly Connected Components (SCCs) partition a directed graph into maximal groups where every vertex can reach every other vertex in the group.