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.

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

---

🔲 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.

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

5. Wildcard Matching – Pattern matching with and ?.

   My Solution: View on GitHub

---

🧱 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.

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

---

🎒 4. Knapsack DP

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

1. Ones and Zeroes – Pick items with max value without exceeding weight.

   My Solution: View on GitHub

2. Last Stone Weight II – Can we make a given sum using a subset?

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

5. Profitable Schemes – Count how many subsets reach a given sum.

   My Solution: View on GitHub

---

📈 5. Longest Increasing Subsequence (LIS)

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

   My Solution: View on GitHub

2. Longest Unequal Adjacent Groups Subsequence II – LIS

   My Solution: View on GitHub

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

   My Solution: View on GitHub

4. Largest Divisible Subset – LIS.

   My Solution: View on GitHub

5. Russian Doll Envelopes – 2D LIS variation.

   My Solution: View on GitHub

---

✍️ 6. Longest Common Subsequence (LCS)

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

---

🔤 7. DP on String

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

---

➕ 8. Cumulative Sum (Prefix Sum + DP)

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

   My Solution: View on GitHub

2. Range Sum Query 2D - Immutable – DP with prefix sums, Segment Tree.

   My Solution: View on GitHub

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

   My Solution: View on GitHub

4. Count Square Submatrices with All Ones – Prefix row sums + DP.

   Solution: View on GitHub

5. Maximal Square - DP.

   My Solution: View on GitHub

---

🧮 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.

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

5. Predict the Winner – We can decide who is win.

   My Solution: View on GitHub

---

⚡ 10. Kadane's Algorithm (Subarray Optimization)

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub

3. Length of Longest Fibonacci Subsequence – Keep track of max length of Fibo sequence

   My Solution: View on GitHub

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

   My Solution: View on GitHub

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

   My Solution: View on GitHub