> ## Documentation Index
> Fetch the complete documentation index at: https://docs.pebchip.top/docs/llms.txt
> Use this file to discover all available pages before exploring further.

# Algorithm Patterns: Dynamic Programming and Graph Algorithms

> Practical algorithm reference with C++ implementations covering dynamic programming, graph theory, greedy algorithms, and competitive programming patterns.

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.

```cpp theme={null}
// 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.

```cpp theme={null}
// 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.

```cpp theme={null}
// 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`:

```cpp theme={null}
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).

```cpp theme={null}
// 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**.

```cpp theme={null}
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.

```cpp theme={null}
// 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.

```cpp theme={null}
// 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)

```cpp theme={null}
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.

```cpp theme={null}
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.

```cpp theme={null}
// 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.

```cpp theme={null}
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`:

```cpp theme={null}
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)]
```

```cpp theme={null}
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

```cpp theme={null}
// 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:

```cpp theme={null}
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.