Dynamic Programming Essentials: Understanding Key Concepts and Exploring DP Variants

---

🧠 What is Dynamic Programming?

Dynamic Programming (DP) is a powerful algorithmic technique that merges the correctness of complete search with the efficiency of greedy algorithms. It is especially useful when a problem can be broken down into overlapping subproblems that can be solved independently and combined for the final solution.

In essence, dynamic programming avoids redundant work by storing solutions to subproblems and reusing them when needed—making it significantly faster than naive recursion or brute-force approaches.

🔍 When to Use Dynamic Programming

Dynamic programming is applicable when:

• The problem has overlapping subproblems (the same subproblem occurs multiple times).

• The problem exhibits optimal substructure (the optimal solution can be constructed from optimal solutions to its subproblems).

Dynamic Programming Approaches: Top-Down vs Bottom-Up

🧠 1. Top-Down Approach (Memoization)

The Top-Down approach, also known as memoization, starts with the original problem and recursively breaks it down into smaller subproblems. It stores the result of each subproblem to avoid redundant calculations.

🔄 How It Works:

• You write a recursive function to solve the problem.

• Before computing a result, check if the result is already in a memoization table.

• If it is, return it.

• If not, compute it and store the result in the memo table.

✅ Pros:

• Easy to implement if you already have a recursive solution.

• Avoids unnecessary computation by only solving subproblems that are actually needed.

🧱 2. Bottom-Up Approach (Tabulation)

The Bottom-Up approach, or tabulation, builds up the solution iteratively from the smallest subproblems. You fill a dp table starting from the base cases.

🔄 How It Works:

• Define a dp[] array (or table).

• Initialize base case(s), e.g., dp[0], dp[1], etc.

• Iterate from smallest to largest subproblems and build the solution using the recurrence.

✅ Pros:

• No recursion overhead, so usually faster and stack-safe.

• Good for problems where all subproblems are needed.

🧪 Example: Fibonacci Numbers and Dynamic Programming

Let’s understand the power of dynamic programming with the Fibonacci sequence.

🔢 Fibonacci Sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The nth Fibonacci number is defined as: fib(n)=fib(n−1)+fib(n−2)

With base cases:

• fib(0) = 0

• fib(1) = 1

❌ Brute Force (Recursive)

Here’s the naive recursive approach:

// C++ program to find Fibonacci number using recursion.
#include <bits/stdc++.h>
using namespace std;

// Function to find nth fibonacci number
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
int main() {
    int n = 4;
    cout << fib(n);// output: 3
    return 0;
}

---

⏱ Time Complexity: O(2ⁿ)

Because each function calls two others → exponential growth.

Below is the recursion tree of the above recursive solution.

How will Dynamic Programming (DP) Work?

Let’s us now see the above recursion tree with overlapping subproblems highlighted with same color. We can clearly see that that recursive solution is doing a lot work again and again which is causing the time complexity to be exponential.

1️⃣ Identify Subproblems

Divide the main problem into smaller, manageable subproblems.

For example, to compute F(n) in the Fibonacci sequence, you need the results of F(n-1) and F(n-2). These are your subproblems.

---

2️⃣ Store Solutions (Memoization)

Solve each subproblem once and save the result in a table (array or map).

This way, if you ever need F(3) again, you can just look it up instead of recalculating it from scratch.

---

3️⃣ Build Up the Solution

Use the stored results to compute the final answer.

For example, once you have F(n-1) and F(n-2) stored, you can compute F(n) = F(n-1) + F(n-2) efficiently.

---

4️⃣ Avoid Recomputations

Dynamic Programming ensures each subproblem is solved only once.

This dramatically reduces time complexity—from exponential to linear in the case of Fibonacci.

✅ Mathematical Recurrence:

$$\text{fib}(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ \text{fib}(n - 1) + \text{fib}(n - 2) & \text{if } n > 1 \end{cases}$$

Using Memoization Approach - O(n) Time and O(n) Space

#include <iostream>
#include <vector>
using namespace std;

int solve(int n, vector<int> &memo) {

    // Base case
    if (n <= 1) {
        return n;
    }

    // To check if output already exists
    if (memo[n] != -1) {
        return memo[n];
    }

    // Calculate and save output for future use
    memo[n] = solve(n - 1, memo) + solve(n - 2, memo);

    return memo[n];
}

int fib(int n) {
    vector<int> memo(n + 1, -1);// we can use vector or map 
    return solve(n, memo);
}

int main() {
    int n = 4;
    cout << fib(n);
    return 0;
}

Using Tabulation Approach - O(n) Time and O(n) Space

#include <iostream>
#include <vector>
using namespace std;

// Function for calculating the nth Fibonacci number
int fibo(int n) {
    vector<int> dp(n + 1);

    // Storing the independent values in dp
    dp[0] = 0;
    dp[1] = 1;

    // Using the bottom-up approach
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

int main() {
    int n = 4;
    cout << fibo(n);
    return 0;
}

Here is a structured guide to master every major Dynamic Programming (DP) category, with 5 carefully selected LeetCode problems per section. These problems are handpicked to help you gradually build intuition and skill in each DP type.

🧱 1. Linear DP (1D DP)

This is the most basic form of DP. We define dp[i] as the optimal answer for the first i elements.

🧪 Core Idea

Build dp[i] using previous states like dp[i-1], dp[i-2], etc.

1. Climbing Stairs – Ways to reach the nth step with 1 or 2 steps at a time.

   My Solution: View on GitHub

2. Fibonacci Numbers – Standard DP recurrence.

3. Min Cost Climbing Stairs – Pay a cost to step; find the minimum total cost.

4. House Robber – Max sum without robbing two adjacent houses.

5. Decode Ways – Count how many ways to decode a numeric string (like '12' → AB or L).

---

🔲 2. 2-Dimensional DP (Table DP)

Used when the state depends on two indices (e.g., ranges, substrings, etc.)

1. Longest Common Subsequence (LCS) – Between two strings.

2. Edit Distance – Minimum operations to convert one string into another.

3. Interleaving Strings – Check if a string is formed by interleaving two others.

4. Distinct Subsequences – Count subsequences of one string that form another.

5. Wildcard Matching – Pattern matching with and ?.

---

🧱 3. DP on Grid

This is a special form of 2D DP, focused on moving in a grid (usually right and down).

1. Unique Paths – Count number of paths from top-left to bottom-right.

2. Minimum Path Sum – Find path with the lowest cost.

3. Coin Change on Grid – Paths with certain weights or restrictions.

4. Grid with Obstacles – Same as Unique Paths but some blocks are disabled.

5. Cherry Pickup – Advanced grid DP with two people collecting cherries.

---

🎒 4. Knapsack DP

Used when we choose items under constraints (weight/volume/cost).

1. 0/1 Knapsack – Pick items with max value without exceeding weight.

2. Subset Sum – Can we make a given sum using a subset?

3. Partition Equal Subset Sum – Can we split an array into two equal-sum parts?

4. Target Sum – Assign + or - to reach a target.

5. Count of Subsets with Given Sum – Count how many subsets reach a given sum.

---

📈 5. Longest Increasing Subsequence (LIS)

1. LIS (O(n^2) and O(n log n)) – Find length of the longest increasing subsequence.

2. Maximum Sum Increasing Subsequence – Max sum instead of length.

3. Number of LIS – Count all increasing subsequences of maximum length.

4. LIS on Circular Array – Wrap-around LIS.

5. Russian Doll Envelopes – 2D LIS variation.

---

✍️ 6. Longest Common Subsequence (LCS)

1. LCS (Basic) – Longest common subsequence of two strings.

2. Shortest Common Supersequence – Shortest string that has both strings as subsequences.

3. Minimum Insertion/Deletion to Make Equal – Using LCS length.

4. Print the LCS – Reconstruct the LCS, not just length.

5. Longest Palindromic Subsequence – LCS of s and reverse(s).

---

🔤 7. DP on String

1. Palindrome Partitioning II – Minimum cuts for palindrome substrings.

2. Regular Expression Matching – Pattern matching with . and .

3. Scramble String – Recursive check using DP and memoization.

4. Word Break – Check if a string can be split into valid dictionary words.

5. Longest Palindromic Substring – Find the longest substring that is a palindrome.

---

➕ 8. Cumulative Sum (Prefix Sum + DP)

1. Range Sum Query – Fast sum queries in a range.

2. Minimum Cost to Merge Stones – DP with prefix sums.

3. Count Subarrays with Sum K – Using prefix sums and hashing.

4. Maximum Sum Rectangle in 2D Matrix – Prefix row sums + Kadane’s.

5. Subarray Sum Equals K – Prefix + hashmap.

---

🧮 9. Matrix Chain Multiplication (Interval DP)

1. Matrix Chain Multiplication – Parenthesize matrix multiplications to minimize cost.

2. Burst Balloons – Choose order to burst balloons to maximize coins.

3. Minimize Cost to Cut a Stick – Optimal way to cut a stick into parts.

4. Palindrome Partitioning – Min cuts to make all substrings palindromes.

5. Boolean Parenthesization – Count ways to parenthesize boolean expressions to be true.

---

⚡ 10. Kadane's Algorithm (Subarray Optimization)

1. Maximum Subarray (Kadane) – Classic problem (LeetCode #53).

2. Maximum Product Subarray – Keep track of min and max.

3. Max Sum Submatrix (2D Kadane) – Extend Kadane to 2D matrix.

4. Best Time to Buy and Sell Stock – DP with max profit difference.

5. Maximum Sum Circular Subarray – Use Kadane twice (normal and inverted).