Dynamic Programming (DP) is a powerful algorithmic technique used to solve optimization problems by breaking them down into simpler subproblems. It is especially useful when a problem has overlapping subproblems and optimal substructure, which allows for the reuse of previously computed solutions to avoid redundant work.

In this blog, we'll explore common dynamic programming patterns along with a categorized list of problems and Java code snippets to help you master DP.

📚 What is Dynamic Programming?

Dynamic programming is a method used to solve problems by breaking them into smaller subproblems and storing the solutions of subproblems to avoid redundant work. It is particularly effective when a problem has the following two characteristics:

  • Optimal Substructure: The optimal solution of the problem can be constructed from optimal solutions of its subproblems.
  • Overlapping Subproblems: The problem can be broken down into smaller subproblems that are solved multiple times.

🔑 Key Components of Dynamic Programming

  1. Memoization: Top-down approach where you store the results of subproblems in a cache (usually an array or a hash map) to avoid recomputation. This is done during recursion.
  2. Tabulation: Bottom-up approach where you solve the problem iteratively and store the solutions in a table (array or matrix), starting from the base case and building up to the solution.

🚀 Common Dynamic Programming Patterns

1. Fibonacci Number

  • Pattern: This is one of the simplest and most well-known examples of DP, where each number is the sum of the two preceding ones. The challenge is to compute the n-th Fibonacci number efficiently by avoiding recalculating intermediate Fibonacci numbers.

Code Example (Fibonacci): 

public class Fibonacci {
    // Using Tabulation (Bottom-up approach)
    public static int fibonacci(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0; // base case
        dp[1] = 1; // base case
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]; // recurrence relation
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci of " + n + " is: " + fibonacci(n));
    }
}

Output: 

Fibonacci of 10 is: 55

2. Knapsack Problem (0/1 Knapsack)

  • Pattern: The knapsack problem involves selecting items with given weights and values to maximize the value that can be carried in a knapsack of limited capacity.
  • Approach: Use a DP table to keep track of the maximum value for each capacity.

Code Example (0/1 Knapsack): 

public class Knapsack {
    // Tabulation approach for 0/1 Knapsack
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 0; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                if (i == 0 || w == 0) {
                    dp[i][w] = 0; // Base case: no items or no capacity
                } else if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        return dp[n][capacity];
    }

    public static void main(String[] args) {
        int[] weights = {1, 2, 3, 8, 4, 5};
        int[] values = {20, 5, 10, 40, 15, 25};
        int capacity = 10;
        System.out.println("Maximum knapsack value: " + knapsack(weights, values, capacity));
    }
}

Output: 

Maximum knapsack value: 60

3. Longest Common Subsequence (LCS)

  • Pattern: The LCS problem involves finding the longest subsequence common to two sequences (e.g., strings). It is useful in tasks like diff algorithms (finding differences between files) or comparing sequences.

Code Example (Longest Common Subsequence): 

public class LCS {
    // Tabulation approach for LCS
    public static int lcs(String str1, String str2) {
        int m = str1.length();
        int n = str2.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 || j == 0) {
                    dp[i][j] = 0; // Base case: empty strings
                } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1; // Characters match
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // No match
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        String str1 = "ABCBDAB";
        String str2 = "BDCAB";
        System.out.println("Longest Common Subsequence length: " + lcs(str1, str2));
    }
}

Output: 

Longest Common Subsequence length: 4

4. Longest Increasing Subsequence (LIS)

  • Pattern: The LIS problem involves finding the length of the longest subsequence in a given array where the elements are strictly increasing.

Code Example (Longest Increasing Subsequence): 

public class LIS {
    // Tabulation approach for LIS
    public static int lis(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // Base case: every element is an increasing subsequence of length 1

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                }
            }
        }

        // Find the maximum length in dp[]
        int max = 1;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
        System.out.println("Longest Increasing Subsequence length: " + lis(arr));
    }
}

Output: 

Longest Increasing Subsequence length: 6

5. Matrix Chain Multiplication

  • Pattern: This problem asks for the most efficient way to multiply a sequence of matrices in order to minimize the total number of scalar multiplications.

Code Example (Matrix Chain Multiplication): 

public class MatrixChain {
    // Tabulation approach for Matrix Chain Multiplication
    public static int matrixChainOrder(int[] dims) {
        int n = dims.length;
        int[][] dp = new int[n][n];

        // dp[i][j] represents the minimum number of multiplications for matrices i to j
        for (int len = 2; len < n; len++) {
            for (int i = 1; i < n - len + 1; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k <= j - 1; k++) {
                    int q = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j];
                    if (q < dp[i][j]) {
                        dp[i][j] = q;
                    }
                }
            }
        }
        return dp[1][n - 1];
    }

    public static void main(String[] args) {
        int[] dims = {1, 2, 3, 4, 3}; // Matrix dimensions: (1x2), (2x3), (3x4), (4x3)
        System.out.println("Minimum number of multiplications: " + matrixChainOrder(dims));
    }
}

Output: 

Minimum number of multiplications: 30

📂 Categories of Dynamic Programming Problems

1. Optimal Substructure Problems

  • Problems that can be broken down into subproblems whose solutions can be combined to solve the overall problem.
  • Examples:
    • Fibonacci Sequence
    • Knapsack Problem
    • Longest Common Subsequence

2. Pathfinding Problems

  • Examples:
    • Grid Path Problem: Finding paths through a grid.
    • Minimum Path Sum: Finding the minimum path sum from the top-left to the bottom-right corner of a grid.

3. Combinatorial Problems

  • Examples:
    • Subset Sum Problem
    • Permutations & Combinations
    • Partition Problem

4. String Problems

  • Examples:
    • Longest Common Subsequence (LCS)
    • Longest Palindromic Subsequence
    • Edit Distance

📝 Conclusion

Dynamic Programming is an essential technique for solving optimization problems efficiently. By breaking down problems into subproblems and reusing solutions to avoid redundant work, DP can significantly reduce time complexity compared to naive approaches.

Mastering common patterns like Fibonacci, Knapsack, LCS, LIS, and Matrix Chain Multiplication will provide a solid foundation in DP. By practicing these patterns, you'll gain the ability to solve complex problems efficiently.

Would you like more examples or specific problems? Let me know in the comments!

This should provide you with a comprehensive understanding of DP and the most common patterns with code examples.