Algorithm Design Paradigms

Dynamic Programming

Solve every distinct subproblem exactly once and cache the result. DP applies precisely when a problem has overlapping subproblems and optimal substructure — the same recursive shape as Divide And Conquer, but with subproblems that recur.

Two required ingredients: overlapping subproblems (the same subproblem is reached via different call paths) and optimal substructure (an optimal solution is built from optimal solutions to subproblems)
Two equivalent implementation styles: top-down memoization (recursion + cache) and bottom-up tabulation (iterate subproblems in dependency order)
The recipe: define the state precisely, write the recurrence relating a state to smaller states, pick a base case, choose an evaluation order
Space is frequently reducible: if the recurrence only looks back a fixed number of rows/states, keep only those instead of the full table
A DP recurrence you can't state in one sentence usually means the state definition is wrong — fix the state before optimizing the code

Memoization vs. tabulation
	Top-down (memoization)	Bottom-up (tabulation)
Structure	recursive function + cache (`Map` or array)	iterative loop filling a table in dependency order
Computes	only the subproblems actually needed	every subproblem up to the target, always
Overhead	recursion + hashing/lookup cost	none — array indexing
Stack risk	can overflow on deep recursion	none
Best when	sparse subproblem space, recurrence is natural to write recursively	dense subproblem space, need max speed or to reconstruct the solution path

Same recurrence, both styles — longest common subsequence

// Top-down: recurse, cache by (i, j)
Map<Long, Integer> memo = new HashMap<>();
int lcs(String a, String b, int i, int j) {
    if (i == a.length() || j == b.length()) return 0;
    long key = (long) i << 32 | j;
    if (memo.containsKey(key)) return memo.get(key);

    int result = a.charAt(i) == b.charAt(j)
        ? 1 + lcs(a, b, i + 1, j + 1)
        : Math.max(lcs(a, b, i + 1, j), lcs(a, b, i, j + 1));
    memo.put(key, result);
    return result;
}

// Bottom-up: fill a table, no recursion
int lcsTabulated(String a, String b) {
    int[][] dp = new int[a.length() + 1][b.length() + 1];
    for (int i = a.length() - 1; i >= 0; i--)
        for (int j = b.length() - 1; j >= 0; j--)
            dp[i][j] = a.charAt(i) == b.charAt(j)
                ? 1 + dp[i + 1][j + 1]
                : Math.max(dp[i + 1][j], dp[i][j + 1]);
    return dp[0][0];
}