Dynamic Programming for Java Developers

Dynamic Programming (DP) is one of the most useful problem-solving techniques in coding interviews and production-grade optimization problems. It often feels difficult at first because many explanations start with formulas instead of intuition.

This guide is designed for Java developers who want a practical, structured, and repeatable way to solve DP problems.

What you will learn:

• How to identify DP problems quickly
• How to define state and recurrence without guesswork
• When to use memoization vs tabulation
• How to optimize space safely
• How to solve common interview patterns in Java

1) What is Dynamic Programming

Dynamic Programming is a way to solve a large problem by solving smaller subproblems once and reusing those answers.

A problem is usually a good DP candidate when both are true:

1. Overlapping subproblems
2. Optimal substructure

Overlapping subproblems

You keep solving the same subproblem repeatedly in a naive recursive approach.

Optimal substructure

The best answer to the full problem can be built from best answers to smaller parts.

2) Quick DP Identification Checklist

If the problem asks for one of these, DP is likely:

• minimum cost
• maximum profit
• number of ways
• can we reach / is it possible
• longest / shortest subsequence or path

If choices are made step by step and each choice affects future states, DP is usually a strong fit.

A quick mental filter: if the problem asks for min, max, count, or feasibility and the same smaller states repeat, DP is usually the right direction.

3) Top-Down vs Bottom-Up

Both solve the same recurrence. Difference is direction.

Top-Down (Memoization)

• write recursive logic first
• cache solved states
• natural and interview-friendly

Bottom-Up (Tabulation)

• start from base cases
• fill table iteratively
• no recursion stack, usually faster runtime in Java

4) 5-Step DP Framework (Use in Every Problem)

1. Define state
2. Write recurrence
3. Set base cases
4. Decide compute order
5. Optimize space if safe

Template thought process:

• State: what does dp[i] or dp[i][j] mean
• Recurrence: how current state depends on previous states
• Base: smallest known states
• Answer: where final value lives

5) Example 1 - Fibonacci (Warm-up)

Problem: Find nth Fibonacci number.

Naive recursion repeats work:

For example, fib(5) recomputes fib(3) and fib(2) multiple times, which is exactly what memoization removes.

State:

• dp[i] = ith Fibonacci number

Recurrence:

• dp[i] = dp[i - 1] + dp[i - 2]

Base:

• dp[0] = 0
• dp[1] = 1

Top-Down Java

import java.util.HashMap;
import java.util.Map;
 
public class FibMemo {
    public int fib(int n) {
        return solve(n, new HashMap<>());
    }
 
    private int solve(int n, Map<Integer, Integer> memo) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);
        int ans = solve(n - 1, memo) + solve(n - 2, memo);
        memo.put(n, ans);
        return ans;
    }
}

Bottom-Up Java

public class FibTab {
    public int fib(int n) {
        if (n <= 1) return n;
        int[] dp = new int[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

public class FibOpt {
    public int fib(int n) {
        if (n <= 1) return n;
        int prev2 = 0;
        int prev1 = 1;
        for (int i = 2; i <= n; i++) {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

Complexity:

• Time O(n)
• Space O(1) optimized

6) Example 2 - Coin Change (Minimum Coins)

Problem: Given coins and amount, return minimum number of coins, or -1.

State:

• dp[a] = minimum coins needed for amount a

Recurrence:

• dp[a] = min(dp[a - coin] + 1) for all valid coins

Base:

• dp[0] = 0

Bottom-Up Java

import java.util.Arrays;
 
public class CoinChange {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
 
        for (int a = 1; a <= amount; a++) {
            for (int coin : coins) {
                if (coin <= a) {
                    dp[a] = Math.min(dp[a], dp[a - coin] + 1);
                }
            }
        }
 
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

Complexity:

• Time O(amount * number_of_coins)
• Space O(amount)

Common bug:

• Using Integer.MAX_VALUE then adding 1 can overflow. Use amount + 1 sentinel.

7) Example 3 - Longest Common Subsequence

Problem: Return length of longest common subsequence of two strings.

State:

• dp[i][j] = LCS length for prefixes s1[0..i-1] and s2[0..j-1]

Recurrence:

• if chars match: dp[i][j] = dp[i - 1][j - 1] + 1
• else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

Base:

• first row and first column are 0

Bottom-Up Java

public class LCS {
    public int lcs(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
 
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

Complexity:

• Time O(m * n)
• Space O(m * n)

Space optimization note

If only length is needed, use 2 rows or 1 row with careful previous diagonal tracking.

8) Example 4 - 0/1 Knapsack

Problem: Maximize value under capacity; each item can be picked at most once.

State:

• dp[i][w] = max value using first i items and capacity w

Choice:

• skip item i
• take item i (if fits)

Bottom-Up Java

public class Knapsack01 {
    public int knapsack(int[] wt, int[] val, int capacity) {
        int n = wt.length;
        int[][] dp = new int[n + 1][capacity + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                int skip = dp[i - 1][w];
                int take = 0;
                if (wt[i - 1] <= w) {
                    take = val[i - 1] + dp[i - 1][w - wt[i - 1]];
                }
                dp[i][w] = Math.max(skip, take);
            }
        }
        return dp[n][capacity];
    }
}

1D optimized version

public class Knapsack01Opt {
    public int knapsack(int[] wt, int[] val, int capacity) {
        int[] dp = new int[capacity + 1];
 
        for (int i = 0; i < wt.length; i++) {
            for (int w = capacity; w >= wt[i]; w--) {
                dp[w] = Math.max(dp[w], val[i] + dp[w - wt[i]]);
            }
        }
        return dp[capacity];
    }
}

Important:

• For 0/1 knapsack in 1D, iterate capacity backward.
• Forward iteration turns it into unbounded behavior.

9) Pattern Map for Interviews

Common DP patterns for Java interviews:

1. Linear DP

   • fibonacci
   • climbing stairs
   • house robber

2. Grid DP

   • unique paths
   • minimum path sum

3. String DP

   • LCS
   • edit distance
   • word break

4. Knapsack family

   • 0/1 knapsack
   • subset sum
   • partition equal subset sum

5. Sequence DP

   • LIS
   • maximum subarray

10) Common Mistakes and Fixes

Mistake 1: Wrong state definition

• Fix: write one clear sentence for state before coding.

Mistake 2: Missing base cases

• Fix: manually test n = 0 and n = 1 first.

Mistake 3: Wrong transition order

• Fix: verify dependencies and table fill direction.

Mistake 4: Overflow or invalid sentinel

• Fix: use safe sentinel values and guard conditions.

Mistake 5: Premature optimization

• Fix: get correct 2D solution first, then optimize.

11) Interview-Ready DP Workflow

Use this in live coding:

1. Say the state out loud
2. Derive recurrence with one small example
3. Write base cases
4. Implement top-down quickly
5. Convert to bottom-up if asked
6. Discuss complexity and possible optimizations

This communication pattern is often as important as the final code.

12) Practice Roadmap

Beginner:

• LeetCode 70 Climbing Stairs
• LeetCode 198 House Robber
• LeetCode 746 Min Cost Climbing Stairs

Intermediate:

• LeetCode 322 Coin Change
• LeetCode 62 Unique Paths
• LeetCode 139 Word Break
• LeetCode 300 LIS

Advanced:

• LeetCode 1143 LCS
• LeetCode 72 Edit Distance
• LeetCode 416 Partition Equal Subset Sum
• LeetCode 312 Burst Balloons

Final Summary

Dynamic Programming becomes manageable when you stop memorizing and start following a framework.

• Define state clearly
• Build recurrence from choices
• Set base cases correctly
• Choose memoization or tabulation
• Optimize space only after correctness

If you can consistently apply this process, you can solve most interview DP problems in Java with confidence.