Algorithm Patterns: Dynamic Programming and Graph Algorithms

Strong algorithm knowledge separates engineers who can solve a problem from those who can solve it efficiently under constraints. This page covers the patterns that appear most frequently in both competitive programming and real system design: dynamic programming in its several forms, graph traversal and shortest paths, greedy reasoning, and mathematical foundations like modular inverse and fast exponentiation. All code examples are in C++ and come directly from the source notes.

Dynamic Programming Patterns

Dynamic programming (DP) solves optimization and counting problems by breaking them into overlapping subproblems, solving each once, and storing the results. The key insight is that optimal substructure holds: the optimal solution to the whole problem can be built from optimal solutions to subproblems.

Classic DP

0/1 Knapsack: given n items with weights and values, and a capacity W, choose items to maximize total value without exceeding W.

// f[j] = max value using exactly capacity j
// Process items one by one; iterate capacity in reverse to prevent reuse
for (int i = 1; i <= n; i++)
    for (int j = W; j >= w[i]; j--)
        f[j] = max(f[j], f[j - w[i]] + v[i]);

Grouped Knapsack: items come in groups; you pick at most one item per group.

// Outer loop: groups; inner loops: capacity (descending), then items in group
for (int i = 1; i <= n; i++)          // group i
    for (int j = m; j >= 1; j--)      // capacity descending
        for (int k = 0; k <= ed[i]; k++)  // items in group
            if (j - k >= 0)
                f[j] = max(f[j - k] + val[i][k], f[j]);

Longest Common Subsequence (LCS): length of the longest subsequence common to two strings.

dp[i][j] = dp[i-1][j-1] + 1           if s1[i] == s2[j]
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) otherwise

Longest Increasing Subsequence (LIS): length of the longest strictly increasing subsequence. Naive DP is O(n²); the patience sort / binary search optimization brings it to O(n log n).

Digit DP

Digit DP counts integers in a range [a, b] that satisfy a digit-level constraint (e.g., digits are non-decreasing, digit sum divisible by m). The standard template uses a dfs(pos, state, limit) function with memoization. Core idea: build the number digit by digit from the most significant position. At each position you may place any digit from 0 to 9 (or 0 to A[pos] if you are still tight against the upper bound). The limit flag tracks whether you are still constrained by the upper bound. Critical rule: you can only memoize a state when limit == false. When limit == true the valid digit range is restricted to A[pos], so the same (pos, state) pair may have a different answer depending on the path taken—memoizing it would produce wrong results.

// Example: count non-decreasing numbers in [a, b]
const int N = 13;
int A[N], cnt;
int dp[N][N]; // dp[pos][last digit placed]

int dfs(int pos, int last, int limit) {
    if (pos == cnt) return 1;  // valid number formed

    // Only cache when not limited; limited states depend on A[pos]
    if (!limit && dp[pos][last] != -1) return dp[pos][last];

    int ans = 0;
    int up = limit ? A[pos] : 9;
    for (int i = last; i <= up; i++)           // non-decreasing: start from last
        ans += dfs(pos + 1, i, limit && i == up);

    if (!limit) dp[pos][last] = ans;           // ONLY cache non-limited states
    return ans;
}

long long f(long long x) {
    cnt = 0;
    memset(dp, -1, sizeof(dp));
    memset(A, 0, sizeof(A));
    while (x) A[cnt++] = x % 10, x /= 10;
    reverse(A, A + cnt);
    return dfs(0, 0, true);
}

// Answer for [a, b]:
cout << f(b) - f(a - 1) << endl;

A variant that tracks digit sum modulo mod:

int dp[N][M]; // dp[pos][sum so far]
int mod;

int dfs(int pos, int sum, int limit) {
    if (pos == cnt) return sum % mod == 0;

    if (!limit && dp[pos][sum] != -1)
        return dp[pos][sum];

    int ans = 0;
    int up = limit ? A[pos] : 9;
    for (int i = 0; i <= up; i++)
        ans += dfs(pos + 1, sum + i, limit && i == up);

    // Only update cache when NOT limited
    if (!limit) dp[pos][sum] = ans;
    return ans;
}

If you accidentally write if (limit) instead of if (!limit) when checking whether to skip the memoization update, the cache will still produce correct values—but the time complexity degrades from polynomial to factorial because the pruning never fires.

Tree DP

Tree DP defines state on each subtree and transitions up to the parent via DFS. The standard form uses f[u][0] / f[u][1] to represent two choices at each node (e.g., selected / not selected in an independent set).

// f[u][0] = best value in subtree u, NOT selecting u
// f[u][1] = best value in subtree u, selecting u
function<void(int, int)> dfs = [&](int u, int p) {
    // traverse children
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == p) continue;
        dfs(j, u);
        f[u][0] += max(f[j][0], f[j][1]);  // u not selected: child can be either
        f[u][1] += f[j][0];                 // u selected: child must not be selected
    }
};

Exchange root DP (also called rerooting): when you need to answer queries rooted at every vertex, run one DFS downward then one DFS upward, propagating information from subtrees into the parent’s “complement subtree.”

Interval DP

Interval DP solves problems over contiguous subarrays. The outer loop iterates over interval length; the inner loop over starting positions; the innermost loop over split points.

for (int len = 2; len <= n; len++)           // interval length
    for (int i = 1; i + len - 1 <= n; i++) { // starting index
        int j = i + len - 1;                  // ending index
        for (int k = i; k < j; k++)           // split point
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i, j));
    }

Classic applications: matrix chain multiplication, optimal BST, burst balloons, palindrome partitioning.

Graph Algorithms

BFS and DFS

BFS explores a graph level by level using a queue, finding shortest paths by hop count in O(V + E). DFS explores deeply before backtracking using a stack (or recursion), useful for topological order, cycle detection, and generating all paths. Multi-source BFS: initialize the queue with multiple source nodes simultaneously. All sources start at distance 0. This solves “nearest X to each cell” problems in a single BFS pass.

Dijkstra’s Algorithm

Dijkstra finds the single-source shortest paths in a graph with non-negative edge weights. It uses a greedy strategy: always relax the unvisited node with the smallest current distance.

// Heap-optimized Dijkstra — O((V + E) log V)
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
typedef pair<int, int> PII;  // (distance, node)

vector<PII> adj[N];          // adj[u] = {(w, v), ...}
int dist[N];

void dijkstra(int src, int n) {
    fill(dist, dist + n + 1, INF);
    dist[src] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;  // stale entry

        for (auto [w, v] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

Dijkstra fails when negative edges exist. Use Bellman-Ford or SPFA instead.

Floyd-Warshall Algorithm

Floyd-Warshall computes all-pairs shortest paths in O(V³) using DP over intermediate nodes.

// Initialize: dist[i][j] = edge weight if edge exists, INF otherwise, 0 on diagonal
for (int k = 1; k <= n; k++)
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= n; y++)
            dist[x][y] = min(dist[x][y], dist[x][k] + dist[k][y]);

After the triple loop, dist[x][y] holds the shortest path between every pair. Floyd-Warshall handles negative edges but not negative cycles. Run it on dense graphs or when you need all-pairs results.

Topological Sort (Kahn’s Algorithm)

vector<int> toposort(int n, vector<vector<int>>& adj) {
    vector<int> indegree(n + 1, 0);
    for (int u = 1; u <= n; u++)
        for (int v : adj[u]) indegree[v]++;

    queue<int> q;
    for (int u = 1; u <= n; u++)
        if (indegree[u] == 0) q.push(u);

    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indegree[v] == 0) q.push(v);
    }

    // If order.size() < n, graph has a cycle
    return order;
}

Applications: build dependency resolution, course scheduling, detecting cycles in directed graphs.

Greedy Algorithms

A greedy algorithm makes a locally optimal choice at each step, hoping to find a global optimum. Greedy works when the greedy choice property holds (a locally optimal choice leads to a globally optimal solution) and the problem has optimal substructure.

Activity Selection / Maximum Non-Overlapping Intervals

Given intervals, select the maximum number of non-overlapping intervals. Greedy rule: always pick the interval that ends earliest. Sort by end time; scan left to right, adding an interval only if its start is ≥ the end of the last selected interval.

sort(intervals.begin(), intervals.end(),
     [](auto& a, auto& b){ return a.second < b.second; });

int count = 0, last_end = INT_MIN;
for (auto& [start, end] : intervals) {
    if (start >= last_end) {
        count++;
        last_end = end;
    }
}

Time: O(n log n) for sorting, O(n) for the scan.

Invariant / Potential-Based Greedy

Some greedy problems require finding a non-obvious invariant. A classic example: given two arrays A and B that can be transformed via adjacent swaps, determine whether A can become B and find the minimum number of swaps. Key insight: define the potential (index + value) array. Arrays A and B can be transformed into each other if and only if their potential multisets are equal. To minimize swaps, use a greedy “nearest first” strategy combined with a BIT (Binary Indexed Tree / Fenwick Tree) to count inversions efficiently.

// Potential of array a: {a[i] + i} for all i
for (int i = 1; i <= n; i++) A.insert(a[i] + i);
for (int i = 1; i <= n; i++) B.insert(b[i] + i);
if (A != B) { cout << -1; return; }

Common Greedy Patterns

Problem type	Greedy rule
Interval scheduling	Sort by end time, pick earliest-ending non-conflicting interval
Interval covering	Sort by start, pick the interval with the farthest reach
Fractional knapsack	Sort by value/weight ratio, take greedily
Huffman coding	Always merge the two lowest-frequency nodes
Minimize maximum	Binary search on the answer + greedy feasibility check

Mathematical Algorithms

Fast Exponentiation (Binary Exponentiation)

Computes base^exp mod m in O(log exp) time by repeatedly squaring.

long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

Modular Inverse

The modular inverse of a mod m is the value x such that a * x ≡ 1 (mod m). It exists when gcd(a, m) = 1. When m is prime, Fermat’s little theorem gives: a^(m-1) ≡ 1 (mod m), so the inverse is a^(m-2) mod m:

long long inv(long long a, long long mod) {
    return power(a, mod - 2, mod);  // only valid when mod is prime
}

For non-prime moduli, use the extended Euclidean algorithm.

Matrix Exponentiation

When a recurrence can be expressed as matrix multiplication, fast exponentiation on matrices reduces O(n) DP to O(m³ log n) where m is the state dimension. Fibonacci example: the Fibonacci recurrence F(n) = F(n-1) + F(n-2) maps to:

[F(n)  ]   [1 1]^(n-1)   [F(2)]
[F(n-1)] = [1 0]       × [F(1)]

struct Matrix { long long a, b, c, d; };
const long long MOD = 1e9 + 7;

Matrix multiply(Matrix m1, Matrix m2) {
    return {
        (m1.a * m2.a + m1.b * m2.c) % MOD,
        (m1.a * m2.b + m1.b * m2.d) % MOD,
        (m1.c * m2.a + m1.d * m2.c) % MOD,
        (m1.c * m2.b + m1.d * m2.d) % MOD
    };
}

Matrix power(Matrix m, long long n) {
    Matrix res = {1, 0, 0, 1};  // identity matrix
    while (n > 0) {
        if (n & 1) res = multiply(res, m);
        m = multiply(m, m);
        n >>= 1;
    }
    return res;
}

long long fibonacci(long long n) {
    Matrix M = {1, 1, 1, 0};
    Matrix Mn = power(M, n);
    return (Mn.a * 1 + Mn.b * 1) % MOD;  // F(2)=1, F(1)=1
}

The same technique applies to any linear recurrence, to counting paths in a graph in exactly k steps, and to computing sums of recurrences modulo a prime.

GCD and LCM

// Euclidean algorithm — O(log min(a, b))
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;  // divide first to avoid overflow
}

Combinatorics with Precomputed Factorials

For problems requiring C(n, k) mod p frequently, precompute factorials and inverse factorials:

const int MAXN = 1e6 + 5;
const long long MOD = 1e9 + 7;
long long fact[MAXN], inv_fact[MAXN];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;
    inv_fact[MAXN-1] = power(fact[MAXN-1], MOD - 2, MOD);
    for (int i = MAXN-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] % MOD * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}

This gives O(1) per query after O(n) precomputation, which is necessary for problems with up to 10^6 combinatorial queries.

Get Started

Databases

Backend Engineering

Computer Science

Software Design

Algorithm Patterns: Dynamic Programming and Graph Algorithms

Dynamic Programming Patterns

Classic DP

Digit DP

Tree DP

Interval DP

Graph Algorithms

BFS and DFS

Dijkstra’s Algorithm

Floyd-Warshall Algorithm

Topological Sort (Kahn’s Algorithm)

Greedy Algorithms

Activity Selection / Maximum Non-Overlapping Intervals

Invariant / Potential-Based Greedy

Common Greedy Patterns

Mathematical Algorithms

Fast Exponentiation (Binary Exponentiation)

Modular Inverse

Matrix Exponentiation

GCD and LCM

Combinatorics with Precomputed Factorials

​Dynamic Programming Patterns

​Classic DP

​Digit DP

​Tree DP

​Interval DP

​Graph Algorithms

​BFS and DFS

​Dijkstra’s Algorithm

​Floyd-Warshall Algorithm

​Topological Sort (Kahn’s Algorithm)

​Greedy Algorithms

​Activity Selection / Maximum Non-Overlapping Intervals

​Invariant / Potential-Based Greedy

​Common Greedy Patterns

​Mathematical Algorithms

​Fast Exponentiation (Binary Exponentiation)

​Modular Inverse

​Matrix Exponentiation

​GCD and LCM

​Combinatorics with Precomputed Factorials

Dynamic Programming Patterns

Classic DP

Digit DP

Tree DP

Interval DP

Graph Algorithms

BFS and DFS

Dijkstra’s Algorithm

Floyd-Warshall Algorithm

Topological Sort (Kahn’s Algorithm)

Greedy Algorithms

Activity Selection / Maximum Non-Overlapping Intervals

Invariant / Potential-Based Greedy

Common Greedy Patterns

Mathematical Algorithms

Fast Exponentiation (Binary Exponentiation)

Modular Inverse

Matrix Exponentiation

GCD and LCM

Combinatorics with Precomputed Factorials