🚀 Blog 12: Dynamic Programming (Mega Edition)

This content originally appeared on DEV Community and was authored by DevCorner2

Dynamic Programming (DP) is the crown jewel of interviews — especially at Expedia where optimization, state transitions, and recursive problem solving are core skills.

This blog is your one-stop DP handbook: from basics → classics → advanced problems.

🔹 1. What is DP?

DP = Overlapping Subproblems + Optimal Substructure

Recursion → Brute force (exponential)
Memoization (Top-Down) → Cache results, cut overlap
Tabulation (Bottom-Up) → Iterative, space-optimized

🔹 2. Fibonacci (Classic Warm-up)

// Recursion + Memoization
class Fibonacci {
    static int fib(int n, int[] dp) {
        if (n <= 1) return n;
        if (dp[n] != -1) return dp[n];
        return dp[n] = fib(n-1, dp) + fib(n-2, dp);
    }

    public static void main(String[] args) {
        int n = 10;
        int[] dp = new int[n+1];
        Arrays.fill(dp, -1);
        System.out.println(fib(n, dp)); // 55
    }
}

✅ Interview insight: Always show both memoization and tabulation approaches.

🔹 3. 0/1 Knapsack

class Knapsack {
    static int knapSack(int W, int[] wt, int[] val, 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 (wt[i-1] <= w)
                    dp[i][w] = Math.max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
                else
                    dp[i][w] = dp[i-1][w];
            }
        }
        return dp[n][W];
    }

    public static void main(String[] args) {
        int[] val = {60, 100, 120};
        int[] wt = {10, 20, 30};
        System.out.println(knapSack(50, wt, val, 3)); // 220
    }
}

✅ Use cases: Budget optimization, subset decisions.

🔹 4. Subset Sum & Partition Problem

class SubsetSum {
    static boolean subsetSum(int[] nums, int sum) {
        int n = nums.length;
        boolean[][] dp = new boolean[n+1][sum+1];
        for (int i = 0; i <= n; i++) dp[i][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (nums[i-1] <= j)
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
        return dp[n][sum];
    }

    public static void main(String[] args) {
        int[] nums = {1, 5, 11, 5};
        int total = Arrays.stream(nums).sum();
        System.out.println(total % 2 == 0 && subsetSum(nums, total/2)); // true
    }
}

✅ Expedia loves this — flight allocation, equal partitioning.

🔹 5. Longest Common Subsequence (LCS)

class LCS {
    static int lcs(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[][] dp = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; 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[n][m];
    }

    public static void main(String[] args) {
        System.out.println(lcs("abcde", "ace")); // 3
    }
}

✅ Variants Expedia asks:

LPS (Longest Palindromic Subsequence)
Edit Distance (Levenshtein)
Shortest Common Supersequence

🔹 6. Longest Increasing Subsequence (LIS)

class LIS {
    static int lis(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int max = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] nums = {10,9,2,5,3,7,101,18};
        System.out.println(lis(nums)); // 4
    }
}

✅ Optimizable to O(n log n) using binary search.

🔹 7. Matrix DP (Grid Problems)

Minimum Path Sum

class MinPathSum {
    static int minPathSum(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][] dp = new int[n][m];
        dp[0][0] = grid[0][0];

        for (int i = 1; i < n; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
        for (int j = 1; j < m; j++) dp[0][j] = dp[0][j-1] + grid[0][j];

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[n-1][m-1];
    }

    public static void main(String[] args) {
        int[][] grid = {{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(minPathSum(grid)); // 7
    }
}

✅ Use cases: Expedia trip cost minimization, optimal routes.

🔹 8. String DP — Edit Distance

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

        for (int i = 0; i <= n; i++) dp[i][0] = i;
        for (int j = 0; j <= m; j++) dp[0][j] = j;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                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[n][m];
    }

    public static void main(String[] args) {
        System.out.println(minDistance("horse", "ros")); // 3
    }
}

✅ Expedia uses this in string similarity / spell correction systems.

🔹 9. Advanced DP — Bitmask DP (TSP Lite)

class TSP {
    static int tsp(int[][] dist, int mask, int pos, int[][] dp) {
        int n = dist.length;
        if (mask == (1<<n)-1) return dist[pos][0]; // return to start
        if (dp[mask][pos] != -1) return dp[mask][pos];

        int ans = Integer.MAX_VALUE;
        for (int city = 0; city < n; city++) {
            if ((mask & (1<<city)) == 0) {
                ans = Math.min(ans, dist[pos][city] +
                        tsp(dist, mask | (1<<city), city, dp));
            }
        }
        return dp[mask][pos] = ans;
    }

    public static void main(String[] args) {
        int[][] dist = {{0,20,42,25},{20,0,30,34},{42,30,0,10},{25,34,10,0}};
        int n = dist.length;
        int[][] dp = new int[1<<n][n];
        for (int[] row : dp) Arrays.fill(row, -1);
        System.out.println(tsp(dist, 1, 0, dp)); // 85
    }
}

✅ Bitmask DP often comes up in Expedia optimization questions.

📊 Key Takeaways for Expedia DP Rounds

Start small → recursive brute force.
Upgrade to memoization → show caching.
End with tabulation + space optimization.
Cover classic problems (Knapsack, LCS, LIS, Matrix, String).
Know 1–2 advanced techniques (Bitmask DP).

👉 In Blog 13, we’ll tackle Heap & Priority Queue patterns — Expedia loves problems on intervals, scheduling, top-k queries, and streaming data.

This content originally appeared on DEV Community and was authored by DevCorner2

Print Share Comment Cite Upload Translate Updates

APA

DevCorner2 | Sciencx (2025-08-26T08:50:38+00:00) 🚀 Blog 12: Dynamic Programming (Mega Edition) — DSA Prep. Retrieved from https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-12-dynamic-programming-mega-edition-dsa-prep/

MLA

" » 🚀 Blog 12: Dynamic Programming (Mega Edition) — DSA Prep." DevCorner2 | Sciencx - Tuesday August 26, 2025, https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-12-dynamic-programming-mega-edition-dsa-prep/

HARVARD

DevCorner2 | Sciencx Tuesday August 26, 2025 » 🚀 Blog 12: Dynamic Programming (Mega Edition) — DSA Prep., viewed ,<https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-12-dynamic-programming-mega-edition-dsa-prep/>

VANCOUVER

DevCorner2 | Sciencx - » 🚀 Blog 12: Dynamic Programming (Mega Edition) — DSA Prep. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-12-dynamic-programming-mega-edition-dsa-prep/

CHICAGO

" » 🚀 Blog 12: Dynamic Programming (Mega Edition) — DSA Prep." DevCorner2 | Sciencx - Accessed . https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-12-dynamic-programming-mega-edition-dsa-prep/

IEEE

" » 🚀 Blog 12: Dynamic Programming (Mega Edition) — DSA Prep." DevCorner2 | Sciencx [Online]. Available: https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-12-dynamic-programming-mega-edition-dsa-prep/. [Accessed: ]

rf:citation

» 🚀 Blog 12: Dynamic Programming (Mega Edition) — DSA Prep | DevCorner2 | Sciencx | https://www.scien.cx/2025/08/26/%f0%9f%9a%80-blog-12-dynamic-programming-mega-edition-dsa-prep/ |

Please log in to upload a file.

There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.