🚀 Blog 2: Dynamic Programming — Expedia DSA Patterns

Dynamic Programming (DP) is one of the most tested patterns at Expedia. Expect medium-level problems where brute force is too slow, and optimization via overlapping subproblems + optimal substructure is key.

We’ll cover:

1. Coin Change (Min Coins)
2. Minimum Path Sum in Triangle
3. Partition Array for Max Sum

---

🔹 Problem 1: Coin Change (Min Coins)

Pattern: Unbounded Knapsack

📌 Find the minimum number of coins needed to make a given amount.

import java.util.*;

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 coin : coins) {
            for (int i = coin; i <= amount; 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(coinChange(coins, 11)); // 3 (5+5+1)
    }
}

✅ Time Complexity: O(N × Amount)

---

🔹 Problem 2: Minimum Path Sum in Triangle

Pattern: Bottom-Up DP

📌 Each step, move to adjacent numbers in the next row. Find minimum path sum from top to bottom.

import java.util.*;

public class TriangleMinPath {
    public static int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n + 1];

        for (int i = n - 1; i >= 0; i--) {
            List<Integer> row = triangle.get(i);
            for (int j = 0; j < row.size(); j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + row.get(j);
            }
        }

        return dp[0];
    }

    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(Arrays.asList(2));
        triangle.add(Arrays.asList(3,4));
        triangle.add(Arrays.asList(6,5,7));
        triangle.add(Arrays.asList(4,1,8,3));

        System.out.println(minimumTotal(triangle)); // 11
    }
}

✅ Time Complexity: O(N²), Space O(N)

---

🔹 Problem 3: Partition Array for Maximum Sum

Pattern: DP with Partitioning

📌 Split the array into subarrays of length ≤ K, replace each subarray with its max element, and maximize the sum.

public class PartitionArrayMaxSum {
    public static int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            int maxVal = 0;
            for (int len = 1; len <= k && i - len >= 0; len++) {
                maxVal = Math.max(maxVal, arr[i - len]);
                dp[i] = Math.max(dp[i], dp[i - len] + maxVal * len);
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int[] arr = {1,15,7,9,2,5,10};
        System.out.println(maxSumAfterPartitioning(arr, 3)); // 84
    }
}

✅ Time Complexity: O(N × K)

---

📊 Expedia DP Key Insights

• Coin Change variants (min coins, count combinations) are very common.
• Triangle/Matrix path problems test bottom-up vs top-down DP.
• Partition DP (breaking array into chunks for optimal result) shows up in Expedia SDE interviews.

---

👉 In Blog 3, we’ll tackle Linked List patterns (Merge, Add Two Numbers, Reverse) — another Expedia favorite.

---