Dynamic Programming Revision (Recognising and Framing DP Problems)

• Optimal substructure – the optimal solution is built from optimal solutions to subproblems.
• Overlapping subproblems – a naive recursion solves the same subproblem multiple times.
• State – the minimal set of parameters that uniquely identifies a subproblem.
• Transition – the recurrence expressing a state's answer in terms of smaller states.
• Base cases – states whose answers are known without recursion.
• Implementation – memoization (top-down with cache) or tabulation (bottom-up with table).

What makes a problem suitable for dynamic programming?

A problem is a dynamic programming candidate when it has two properties. Optimal substructure means the optimal answer can be expressed as a combination of optimal answers to smaller subproblems. Overlapping subproblems means a naive recursion would solve the same subproblem multiple times.

When both properties hold, caching subproblem results converts exponential brute-force recursion into polynomial-time computation. If only optimal substructure holds (no overlap), divide-and-conquer suffices. If neither holds, DP does not apply.

package com.bank.dsa;

// Fibonacci: both properties hold
public class DpRecognition {

    // Optimal substructure: fib(n) = fib(n-1) + fib(n-2)
    // Overlapping subproblems: fib(3) computed many times in naive recursion
    public static long fibNaive(int n) {
        if (n <= 1) return n;
        return fibNaive(n - 1) + fibNaive(n - 2);
    }

    // DP fix: compute each state once
    public static long fibDp(int n) {
        if (n <= 1) return n;
        long a = 0, b = 1;
        for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }
        return b;
    }

    public static void main(String[] args) {
        System.out.println("Naive fib(10): " + fibNaive(10));
        System.out.println("DP    fib(10): " + fibDp(10));
    }
}

Naive fib(10): 55
DP    fib(10): 55

How do you frame a DP problem?

The framing discipline has four steps:

1. Define the state: the minimal set of parameters that fully describes a subproblem. For knapsack, the state is (item index, remaining capacity). For LCS, it is (index in A, index in B).

2. Write the transition: express the state's answer in terms of strictly smaller states. For Fibonacci: fib(n) = fib(n-1) + fib(n-2). For knapsack: dp[i][c] = max(dp[i-1][c], value[i] + dp[i-1][c - weight[i]]).

3. Fix the base cases: states whose answers are known without recursion. For Fibonacci: fib(0) = 0, fib(1) = 1. For knapsack: dp[0][c] = 0 for all c.

4. Choose implementation: memoization (top-down with cache) or tabulation (bottom-up with table).

package com.bank.dsa;

/**
 * Generic DP skeleton showing the four-step discipline.
 */
public class DpSkeleton {

    // Step 1: State is (remaining amount)
    // Step 2: Transition: dp[a] = min over coins of (1 + dp[a - coin])
    // Step 3: Base: dp[0] = 0
    // Step 4: Tabulation (bottom-up)

    public static int minCoins(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        java.util.Arrays.fill(dp, amount + 1);  // sentinel
        dp[0] = 0;  // base case

        for (int a = 1; a <= amount; a++) {
            for (int coin : coins) {
                if (coin <= a) {
                    dp[a] = Math.min(dp[a], 1 + dp[a - coin]);  // transition
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println("Min coins for 11: " + minCoins(new int[]{1, 5, 6, 9}, 11));
    }
}

Min coins for 11: 2

What are the standard DP patterns?

Most interview DP problems fall into a few recurring patterns:

• Fibonacci Numbers: fixed-window recurrence (climbing stairs, house robber, tribonacci).
• 0/1 Knapsack: binary include-or-exclude under a capacity (subset sum, partition, target sum).
• Unbounded Knapsack: items repeat (coin change, rod cutting, ribbon cutting).
• Longest Common Subsequence: two-sequence grid (edit distance, diff tools).
• Interval DP: split a range at each point (matrix chain, burst balloons, cut a stick).
• Grid Paths: coordinate states (unique paths, minimum path sum).

package com.bank.dsa;

/**
 * Pattern recognition: unique paths in a grid (Grid Paths pattern).
 */
public class UniquePaths {

    public static int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        java.util.Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                dp[j] += dp[j - 1];
        return dp[n - 1];
    }

    public static void main(String[] args) {
        System.out.println("Unique paths 3x7: " + uniquePaths(3, 7));
    }
}

Unique paths 3x7: 28

How do you choose between memoization and tabulation?

| Aspect | Memoization (top-down) | Tabulation (bottom-up) |
|---|---|---|
| Subproblems solved | Only reachable states | All states in the table |
| Stack usage | Recursion stack (risk of overflow) | No recursion |
| Space optimisation | Difficult (stack holds state) | Easy (roll rows, keep last few vars) |
| Code style | Natural for tree-shaped decisions | Natural for sequence/grid problems |
| Performance | Overhead of cache lookups | Tight loops, cache-friendly |

Memoization is preferred when only a fraction of the state space is reachable, or when the recursion structure closely matches the decision process. Tabulation is preferred when the state space is dense, stack depth is a concern, or space optimisation is important.

What is the hardest part of DP?

State design is the hardest part. The state must capture everything needed to extend the solution, but nothing more. A state with too few dimensions gives wrong answers because it conflates distinct subproblems. A state with too many dimensions makes the problem intractable.

For example, in 0/1 Knapsack, the state is (item index, remaining capacity). If you forget the item index and only use capacity, the recursion allows item reuse, silently solving unbounded knapsack.

// WRONG: state is only capacity, items can be reused
public static int wrong(int[] w, int[] v, int cap) {
    if (cap <= 0) return 0;
    int best = 0;
    for (int i = 0; i < w.length; i++)
        if (w[i] <= cap)
            best = Math.max(best, v[i] + wrong(w, v, cap - w[i]));
    return best;  // this is unbounded knapsack!
}

// CORRECT: state includes item index
public static int correct(int[] w, int[] v, int idx, int cap) {
    if (idx >= w.length || cap <= 0) return 0;
    int exc = correct(w, v, idx + 1, cap);
    int inc = w[idx] <= cap ? v[idx] + correct(w, v, idx + 1, cap - w[idx]) : 0;
    return Math.max(exc, inc);
}

What are common mistakes when framing DP?

The most common mistakes are:

• Wrong state: missing a dimension that distinguishes subproblems.
• Missing base cases: every recursion path must reach a base case.
• Wrong transition direction: confusing which states are "smaller".
• Forgetting space optimisation: using O(n^2) when O(n) suffices.
• Not checking the answer location: the answer is not always dp[n] (e.g., LIS uses max over all dp[i]).

How does space optimisation work?

Many 2D DP tables compress to 1D because each row depends only on the previous row. For Fibonacci, two variables suffice. For knapsack, one row swept in the right direction suffices. For LCS, two rows suffice.

package com.bank.dsa;

public class SpaceOptimisation {

    // Full table: O(n) space
    public static long fibArray(int n) {
        if (n <= 1) return n;
        long[] dp = new long[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-optimised: O(1) space
    public static long fibRolling(int n) {
        if (n <= 1) return n;
        long a = 0, b = 1;
        for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }
        return b;
    }

    public static void main(String[] args) {
        System.out.println("Array:   fib(20) = " + fibArray(20));
        System.out.println("Rolling: fib(20) = " + fibRolling(20));
    }
}

Array:   fib(20) = 6765
Rolling: fib(20) = 6765

When should you use DP in banking?

At the National Bank of India, DP appears in many contexts:

• Cash dispensing: minimum coins for an amount (Unbounded Knapsack minimisation).
• Loan allocation: select deals within a budget (0/1 Knapsack).
• Name matching: edit distance for KYC fuzzy match (LCS family).
• Bond splitting: minimum cost to cut denominations (Interval DP).
• Reward projection: Fibonacci-style compounding (Fibonacci pattern).

package com.bank.service;

public class DpInBanking {

    // Cash dispensing: minimum notes
    public static int minNotes(int[] denominations, int amount) {
        int[] dp = new int[amount + 1];
        java.util.Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++)
            for (int d : denominations)
                if (d <= a) dp[a] = Math.min(dp[a], 1 + dp[a - d]);
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println("Min notes for 3700: " + minNotes(new int[]{100, 200, 500, 2000}, 3700));
    }
}

Min notes for 3700: 3

What should a senior engineer know?

A senior engineer should understand that knapsack-style complexities are pseudo-polynomial: O(N * C) depends on the numeric capacity, not the input size in bits. This is why knapsack is NP-hard in general.

The choice between memoization and tabulation is practical, not theoretical. Both give the same asymptotic complexity. Memoization is more natural for tree-shaped problems; tabulation is better for dense state spaces and space optimisation.

Being able to recognise the pattern a problem belongs to (Fibonacci, knapsack, LCS, interval, grid) is half the battle. The other half is correct state design.