Chapter 35: Dynamic Programming Part 3 - Advanced Problems and Techniques

Dynamic Programming (DP) helps solve complex problems by breaking them into manageable subproblems, saving time by reusing solutions. In this chapter, we explore advanced DP problems that frequently appear in competitive programming and real-life applications. Below is a detailed breakdown of each problem, along with well-structured code examples. Let's dive in!

---

1. Coin Change Problem

The Coin Change problem requires finding the number of ways or minimum number of coins needed to make a specific amount using a given set of coin denominations. Here, we focus on finding the minimum number of coins.

Problem Statement

Given an amount A and a list of denominations coins, return the minimum number of coins required to make A.

Approach

We use bottom-up DP to build a table dp where dp[i] represents the minimum number of coins required to make amount i. We initialize dp[0] to 0 because no coins are needed to make 0, and set the rest to a large value (infinity) to represent unreachable amounts.

Code

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); // Initialize with a large value
        dp[0] = 0;

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

        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }

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

---

2. Rod Cutting Problem

The Rod Cutting problem is a classic optimization problem where we aim to maximize the profit by cutting a rod into different lengths, each with an associated price.

Problem Statement

Given a rod of length n and a list of prices for each length, maximize the profit obtained by cutting the rod and selling the pieces.

Approach

Using DP, we define dp[i] as the maximum profit achievable for a rod of length i. For each length i, we consider all possible cuts j and check the best profit by either making a cut at j or not.

Code

public class RodCutting {
    public int rodCutting(int[] prices, int n) {
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            int maxProfit = Integer.MIN_VALUE;
            for (int j = 0; j < i; j++) {
                maxProfit = Math.max(maxProfit, prices[j] + dp[i - j - 1]);
            }
            dp[i] = maxProfit;
        }

        return dp[n];
    }

    public static void main(String[] args) {
        RodCutting rc = new RodCutting();
        int[] prices = {1, 5, 8, 9, 10, 17, 17, 20};
        int length = 8;
        System.out.println("Maximum profit: " + rc.rodCutting(prices, length)); // Output: 22
    }
}

---

3. Longest Common Subsequence (LCS) - Recursive Approach

The Longest Common Subsequence problem seeks to find the longest subsequence common to two strings.

Problem Statement

Given two strings s1 and s2, return the length of the longest subsequence that appears in both strings.

Approach

In the recursive approach, we compare characters from the end of each string. If they match, we include them in our subsequence and move both indices backward. Otherwise, we make two recursive calls to find the longest subsequence.

Code

public class LCSRecursive {
    public int lcs(String s1, String s2) {
        return lcsHelper(s1, s2, s1.length(), s2.length());
    }

    private int lcsHelper(String s1, String s2, int m, int n) {
        if (m == 0 || n == 0) return 0;

        if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
            return 1 + lcsHelper(s1, s2, m - 1, n - 1);
        } else {
            return Math.max(lcsHelper(s1, s2, m, n - 1), lcsHelper(s1, s2, m - 1, n));
        }
    }

    public static void main(String[] args) {
        LCSRecursive lcs = new LCSRecursive();
        String s1 = "ABCBDAB";
        String s2 = "BDCAB";
        System.out.println("LCS length: " + lcs.lcs(s1, s2)); // Output: 4
    }
}

---

4. Longest Common Subsequence (LCS) - Memoization Approach

To improve efficiency, we use memoization to avoid redundant calculations.

Code

import java.util.Arrays;

public class LCSMemoization {
    public int lcs(String s1, String s2) {
        int[][] memo = new int[s1.length() + 1][s2.length() + 1];
        for (int[] row : memo) Arrays.fill(row, -1);
        return lcsHelper(s1, s2, s1.length(), s2.length(), memo);
    }

    private int lcsHelper(String s1, String s2, int m, int n, int[][] memo) {
        if (m == 0 || n == 0) return 0;

        if (memo[m][n] != -1) return memo[m][n];

        if (s1.charAt(m - 1) == s2.charAt(n - 1)) {
            memo[m][n] = 1 + lcsHelper(s1, s2, m - 1, n - 1, memo);
        } else {
            memo[m][n] = Math.max(lcsHelper(s1, s2, m, n - 1, memo), lcsHelper(s1, s2, m - 1, n, memo));
        }
        return memo[m][n];
    }

    public static void main(String[] args) {
        LCSMemoization lcs = new LCSMemoization();
        String s1 = "ABCBDAB";
        String s2 = "BDCAB";
        System.out.println("LCS length: " + lcs.lcs(s1, s2)); // Output: 4
    }
}

---

5. Longest Common Subsequence (LCS) - Tabulation Approach

In the tabulation approach, we build a DP table to avoid recursive calls and improve performance further.

Code

public class LCSTabulation {
    public 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] = 1 + dp[i - 1][j - 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) {
        LCSTabulation lcs = new LCSTabulation();
        String s1 = "ABCBDAB";
        String s2 = "BDCAB";
        System.out.println("LCS length: " + lcs.lcs(s1, s2)); // Output: 4
    }
}

---

Summary

This chapter presented multiple ways to solve fundamental DP problems, each showcasing different aspects of optimization in dynamic programming:

• Coin Change: Optimal use of resources.

• Rod Cutting: Profit maximization.

• LCS (Recursive, Memoized, and Tabulated): Efficient sequence matching.

By mastering these approaches, you’ll be equipped to tackle a wide array of DP problems efficiently!