🎯 Dynamic Programming (DP) – Comprehensive Study Guide

**Dynamic Programming (DP)** is an **optimization technique** used to solve problems by breaking them down into **overlapping subproblems** and storing results to avoid redundant calculations.

⚡ Why Use Dynamic Programming?

• ✅ **Reduces time complexity** compared to recursion.
• 🚀 **Optimizes solutions for combinatorial problems**.
• 🔄 **Efficiently solves overlapping subproblems**.
• 📊 **Used in AI, machine learning, and optimization algorithms**.

📌 Key Differences: Recursion vs Dynamic Programming

🛠️ Types of Dynamic Programming Approaches

📥 1️⃣ **Top-Down Approach (Memoization)**

Uses **recursion + caching** to store previously computed results.

                int dp[100] = { -1 };
            
                int fibonacciMemo(int n) {
                    if (n <= 1) return n;
                    if (dp[n] != -1) return dp[n];  // Use stored result
                    return dp[n] = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
                }
                

📤 2️⃣ **Bottom-Up Approach (Tabulation)**

Solves subproblems **iteratively** and builds solutions step by step.

                int fibonacciTabulation(int n) {
                    int dp[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];
                }
                

✅ **Memoization vs Tabulation**

• 📥 **Memoization** – Uses recursion + caching, needs more stack space.
• 📤 **Tabulation** – Uses iteration, avoids recursion overhead.

🔥 Common DP Problems & Their Solutions

📌 **1. Fibonacci Sequence (O(n))**

Uses **dynamic programming** to optimize recursion.

📌 **2. 0/1 Knapsack Problem (O(nW))**

Finds the **maximum value** we can carry in a **bag of weight W**.

                int knapsack(int W, vector wt, vector val, int n) {
                    int dp[n+1][W+1];
            
                    for (int i = 0; i <= n; i++) {
                        for (int w = 0; w <= W; w++) {
                            if (i == 0 || w == 0)
                                dp[i][w] = 0;
                            else if (wt[i - 1] <= w)
                                dp[i][w] = 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];
                }
                

📌 **3. Longest Common Subsequence (LCS) (O(n²))**

Finds the **longest matching subsequence** between two strings.

                int lcs(string X, string Y, int m, int n) {
                    int dp[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;
                            else if (X[i - 1] == Y[j - 1])
                                dp[i][j] = 1 + dp[i - 1][j - 1];
                            else
                                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                        }
                    }
                    return dp[m][n];
                }
                

📌 **4. Longest Increasing Subsequence (O(n²))**

Finds the **longest increasing sequence** in an array.

⏳ Time Complexity Analysis

🌍 Real-World Applications of DP

• 📡 **AI & Machine Learning** – Predictive analytics.
• 🔍 **Data Compression** – Image & video encoding (JPEG, MP3).
• 📊 **Stock Market Prediction** – Forecasting trends.
• 🎮 **Game Development** – AI-based decision-making.

🔗 Next Topics

• 🔢 Fibonacci Using DP
• 📦 0/1 Knapsack Problem