DP, Bitwise, Recursion¶

Dynamic programming is where study problems get scary and where C actually helps rather than hurts. A 2D int array is a natural memo table, long long covers the overflow cases, and C’s bit operations are direct enough to make bitmask DP feel elegant instead of arcane. This file covers the DP toolkit, the bit tricks you’ll use weekly, and how C’s __builtin_* intrinsics turn some problems into one-liners.

Memoization: The Table Choice¶

Every memoized recursion needs a table. In C, three options in order of preference:

1. Fixed-size 2D array (when dimensions are known at compile time)¶

int memo[1001][1001];
memset(memo, -1, sizeof memo);   // -1 == uncomputed

int solve(int i, int j) {
    if (memo[i][j] != -1) return memo[i][j];
    /* ... compute ... */
    return memo[i][j] = result;
}

Simple. Fast. Uses BSS if declared at file scope. Watch stack size if declared local — int memo[1001][1001] is 4 MB, fine at file scope, dangerous inside main on non-primary threads.

2. Malloc’d flat array with manual indexing¶

For dimensions known only at runtime:

int *memo = malloc((size_t)m * n * sizeof(int));
for (int i = 0; i < m * n; i++) memo[i] = -1;
// index memo[i * n + j] where i is row and j is column

One allocation, no per-row malloc calls, cache-friendly. Standard.

3. Hashmap for sparse state spaces¶

When the state space is huge but only a small fraction is reachable. Rare in studies; use libprep::map.

Bottom-Up vs Top-Down¶

Same problem, two implementations.

Top-down (memoized recursion): intuitive; write the recurrence directly.

int fib(int n) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n-1) + fib(n-2);
}

Bottom-up (iterative table fill): no recursion, no stack risk, often faster.

int fib(int n) {
    int dp[n+1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

Space-optimized bottom-up: notice that dp[i] only depends on dp[i-1] and dp[i-2]. Roll two variables:

int fib(int n) {
    if (n < 2) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) { int t = a + b; a = b; b = t; }
    return b;
}

This rolling-window compression is the #1 space optimization in DP problems. Look for it everywhere.

Integer Overflow in DP¶

The most common bug. “Count the number of ways…” DPs multiply, sum, and iterate; even if each step fits in int, the accumulator can overflow. Use long long:

long long dp[n+1];
// ...
return (int)(dp[n] % 8126311);   // often the answer is asked mod 10^9+7

Unique Paths, Distinct Subsequences, Decode Ways — all overflow int in the general case. Default to long long for DP counter values; convert back at the boundary.

The Classic DP Templates¶

1-D DP¶

dp[i] is the answer for prefix ending at i (or state i). Climbing Stairs, House Robber, Coin Change, Longest Increasing Subsequence.

2-D DP on grids¶

dp[i][j] for state (row, col). Unique Paths, Min Path Sum, Edit Distance, Longest Common Subsequence.

2-D DP on two sequences¶

dp[i][j] for the answer using first i chars of A and first j of B. Edit Distance is the archetype:

int edit_dist(const char *a, const char *b, int m, int n) {
    int dp[m+1][n+1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1];
            else {
                int ins = dp[i][j-1], del = dp[i-1][j], sub = dp[i-1][j-1];
                int m1 = ins < del ? ins : del;
                dp[i][j] = 1 + (m1 < sub ? m1 : sub);
            }
        }
    }
    return dp[m][n];
}

Memorize this shape. Half of “string DP” is variations of it.

Interval DP¶

dp[i][j] is the answer for the subarray arr[i..j]. Length varies from small to large. Matrix Chain Multiplication, Burst Balloons, Palindrome Partitioning II.

for (int len = 2; len <= n; len++) {
    for (int i = 0; i + len <= n; i++) {
        int j = i + len - 1;
        for (int k = i; k < j; k++) {
            /* combine dp[i][k] and dp[k+1][j] */
        }
    }
}

Bitmask DP¶

When the state includes “which subset of N items have we used,” and N ≤ ~20. The state is an int bitmask.

int dp[1 << N];
for (int mask = 0; mask < (1 << N); mask++) {
    for (int i = 0; i < N; i++) {
        if (mask & (1 << i)) {
            /* i is in the set */
        }
    }
}

Uses: Traveling Salesman on small N, “assign N tasks to N workers,” “visit all cities.” C’s bit operations make this clean; Python’s slower per-op cost makes it painful. Bitmask DP is one of the places C is strictly better than Python for solving.

Complexity: O(2ᴿ * N) or O(2ᴿ * N²). For N ≤ 20 that’s 20M or 400M operations — the former runs in ~0.5s in C, ~5s in Python.

Bit Manipulation Toolkit¶

The Idioms Every C Programmer Knows¶

x & (x - 1)          // clears the lowest set bit
x & -x               // isolates the lowest set bit
x | (x + 1)          // sets the lowest zero bit
(x >> i) & 1         // check bit i
x |= (1 << i)        // set bit i
x &= ~(1 << i)       // clear bit i
x ^= (1 << i)        // flip bit i

Counting Set Bits (Brian Kernighan)¶

int popcount(unsigned int x) {
    int c = 0;
    while (x) { x &= x - 1; c++; }   // clears one bit per iteration
    return c;
}

Or, better, the compiler intrinsic:

__builtin_popcount(x)      // unsigned int, returns int
__builtin_popcountll(x)    // unsigned long long

On x86-64 with -march=native, these emit a single POPCNT instruction. In studies, using __builtin_popcount is showing off in a good way — it’s the mark of someone who’s read the compiler manual.

Other Useful Builtins¶

__builtin_ctz(x)      // count trailing zeros (position of lowest set bit)
__builtin_clz(x)      // count leading zeros (32 - bit_length)
__builtin_parity(x)   // parity: 1 if odd number of set bits

__builtin_ctz(x) on 0 is undefined. Guard with if (x).

Two-Complement / Negative Number Facts¶

x & -x isolates the lowest set bit because -x in two’s complement is ~x + 1, which shares the lowest set bit and inverts everything above it.
Shift right of negative numbers is implementation-defined (usually arithmetic — sign-extending). Prefer unsigned for bit-twiddling.
Overflow of signed types on multiplication or addition is undefined behavior. Overflow of unsigned is defined (modular). Bitmask code uses unsigned for this reason.

Recursion in C: Explicit Stack When Needed¶

Recursive DP is elegant but limited by stack depth. When constraints put you at risk:

// Iterative post-order with explicit state machine
typedef struct { int i, j, phase; } Frame;
Stack s = stack_new();
stack_push(&s, (Frame){/* initial */});
while (!stack_empty(&s)) {
    Frame *f = stack_peek(&s);
    switch (f->phase) {
        case 0: /* recurse into left */ f->phase = 1; stack_push(&s, /* left frame */); continue;
        case 1: /* recurse into right */ f->phase = 2; stack_push(&s, /* right frame */); continue;
        case 2: /* combine and pop */ stack_pop(&s); break;
    }
}

Ugly, but sometimes necessary. Reserve for when recursion actually blows up on you.

What Most People Get Wrong About This¶

They pick top-down memoization by default and lose to stack overflow on hard problems, or they pick bottom-up and lose 20 minutes on tricky index bounds when top-down would have been cleaner. The right heuristic: top-down when the recurrence is easier to state than the iteration order; bottom-up when the state space is small and dense. And always ask: can this be space-optimized with a rolling window? For 1-D DPs and 2-D DPs where you only read the previous row, yes — do it and get O(1) or O(n) space.

Return to README.md · Next: 08_interview_patterns_top_20.md