NUHMAN.com

📌 What is Dynamic Programming?

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems — and storing the results to avoid redundant computations.

If you’re preparing for coding interviews or learning algorithmic problem-solving, DP is a must-have tool in your Java toolbox.

📘 1. Fibonacci Sequence – Bottom-Up DP

Instead of recursively recalculating Fibonacci numbers, store them in an array (dp[]) and build from the base case.

java

public class FibonacciDP {
    public static int fibonacci(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];
    }

    public static void main(String[] args) {
        System.out.println("Fibonacci(10): " + fibonacci(10)); // Output: 55
    }
}

🧠 Concept: Bottom-Up Tabulation

Time Complexity: O(n)

Space Complexity: O(n)

🎒 2. 0/1 Knapsack Problem – Maximize Value

Choose items to maximize value in a knapsack of limited weight capacity.

java

public class KnapsackDP {
    public static int knapsack(int[] weights, int[] values, int W, int n) {
        int[][] dp = new int[n + 1][W + 1];

        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= W; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(
                        dp[i - 1][w],
                        dp[i - 1][w - weights[i - 1]] + values[i - 1]
                    );
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }

        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        System.out.println("Max value: " + knapsack(weights, values, 50, weights.length)); // Output: 220
    }
}

🧠 Concept: 2D DP Table

Time Complexity: O(n * W)

Space Complexity: O(n * W)

🔗 3. Longest Common Subsequence (LCS)

Find the length of the longest subsequence common to two strings.

java

public class LCS {
    public static int lcs(String s1, String s2) {
        int m = s1.length(), 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];
    }

    public static void main(String[] args) {
        System.out.println("LCS length: " + lcs("AGGTAB", "GXTXAYB")); // Output: 4
    }
}

🧠 Concept: 2D Matrix to Track Matches

Time Complexity: O(m * n)

Space Complexity: O(m * n)

✍️ 4. Edit Distance (Levenshtein Distance)

Find the minimum number of insertions, deletions, and substitutions to convert one string into another.

java

public class EditDistance {
    public static int editDistance(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++)
            for (int j = 0; j <= n; j++) {
                if (i == 0) dp[i][j] = j;
                else if (j == 0) dp[i][j] = i;
                else if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
                                    Math.min(dp[i - 1][j], dp[i][j - 1]));
            }

        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println("Edit Distance: " + editDistance("sunday", "saturday")); // Output: 3
    }
}

🧠 Concept: 2D Matrix for Minimum Operations

Time Complexity: O(m * n)

Space Complexity: O(m * n)

🪙 5. Coin Change Problem – Fewest Coins

Given coins and a target amount, find the minimum number of coins needed.

java

import java.util.Arrays;

public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++)
            for (int coin : coins)
                if (coin <= i)
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);

        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        System.out.println("Min coins: " + coinChange(coins, 11)); // Output: 3 (5+5+1)
    }
}

🧠 Concept: 1D DP Array

Time Complexity: O(amount × coins.length)

Space Complexity: O(amount)

✅ Summary Table

ProblemApproachTime ComplexitySpace ComplexityFibonacciBottom-Up ArrayO(n)O(n)0/1 Knapsack2D DP TableO(n × W)O(n × W)LCS2D DP TableO(m × n)O(m × n)Edit Distance2D DP TableO(m × n)O(m × n)Coin Change1D DP ArrayO(amount × n)O(amount)

📚 Want to Go Deeper?

• Add memoization (top-down) versions of the problems
• Optimize space (especially for LCS and Edit Distance)
• Try variations like:
• Longest Palindromic Subsequence
• Matrix Chain Multiplication
• Subset Sum