Dynamic Programming Technique in DSA

What is the Dynamic Programming Technique?

Dynamic Programming (DP) is used for solving complex problems by breaking them down into simpler overlapping subproblems and solving each subproblem only once, storing the result for future reuse. This avoids the overhead of recalculating solutions repeatedly (as in recursion).

DP is applicable when the problem has two main properties:

• Overlapping Subproblems: The problem can be broken into smaller subproblems that repeat over time.
• Optimal Substructure: The optimal solution of a problem can be constructed from the optimal solutions of its subproblems.

Top-Down vs Bottom-Up Approach

• Top-Down (Memoization): Solve the problem recursively and store results to avoid duplicate work.
• Bottom-Up (Tabulation): Build the solution iteratively using a table from base case up to the final result.

---

Example 1: Fibonacci Number — Explained for Beginners

Problem Statement:

Find the nth Fibonacci number, where the Fibonacci series is defined as follows:

• F(0) = 0
• F(1) = 1
• F(n) = F(n - 1) + F(n - 2) for n ≥ 2

This means each number in the sequence is the sum of the two previous numbers. For example, the first few Fibonacci numbers are:

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

Why Not Use Simple Recursion?

If we write a simple recursive solution like:

function fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

This looks clean, but it's extremely inefficient because it recalculates the same values again and again. For example, fib(5) will compute fib(4) and fib(3), but then fib(4) again computes fib(3) and fib(2) — so fib(3) is computed twice. The number of recursive calls grows exponentially.

This is where Dynamic Programming helps.

Dynamic Programming solves this problem by storing solutions to subproblems so we don’t compute them again. Let’s explore both top-down and bottom-up DP approaches:

Top-Down DP Approach (Memoization)

We use recursion, but we store the result of each Fibonacci number we calculate in a dictionary (called memo). Before computing any value, we check if it’s already in memo and use it directly if found.

Step-by-step Explanation:

1. Start from fib(n).
2. Check if n is already in memo. If yes, return it.
3. If n is 0 or 1, return n (base case).
4. Otherwise, compute fib(n-1) and fib(n-2).
5. Store their sum in memo[n].
6. Return memo[n].

Pseudocode

// Memoization approach
function fib(n, memo):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

Why It Works:

Each Fibonacci number is calculated only once and reused wherever needed. This avoids redundant calculations.

Time Complexity:

• O(n) — each number is computed once and stored.

Space Complexity:

• O(n) — to store memo.

Bottom-Up DP Approach (Tabulation)

Instead of starting from the top and going down recursively, we start from the bottom (base cases) and build up the solution iteratively.

Step-by-step Explanation:

1. Create a table dp[] of size n+1 to store Fibonacci values.
2. Initialize: dp[0] = 0 and dp[1] = 1.
3. Iterate from i = 2 to n.
4. At each step, calculate dp[i] = dp[i-1] + dp[i-2].
5. Return dp[n] as the final result.

Pseudocode

// Tabulation approach
function fib(n):
    if n <= 1:
        return n
    dp = array of size (n+1)
    dp[0] = 0
    dp[1] = 1
    for i from 2 to n:
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Why It Works:

This method uses an iterative approach and solves the subproblems first before combining them to solve the main problem.

Time Complexity:

• O(n) — we compute each Fibonacci number from 2 to n once.

Space Complexity:

• O(n) — for the dp array (can be optimized to O(1) by storing only last two values).

The Fibonacci number problem is a great way to understand dynamic programming. It highlights the idea of breaking a problem into smaller subproblems and using stored results to avoid recomputation. For beginners, this teaches how to recognize overlapping subproblems and how memoization and tabulation can drastically improve performance.

---

// Bottom-up 2D DP
function knapsack(weights, values, n, W):
    dp = 2D array of size (n+1) x (W+1)
    for i from 0 to n:
        for w from 0 to W:
            if i == 0 or w == 0:
                dp[i][w] = 0
            else if weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w - weights[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

Example 3: Longest Common Subsequence (LCS)

Problem Statement: Given two strings, find the length of the Longest Common Subsequence (LCS) present in both. A subsequence is a sequence that appears in the same relative order but not necessarily contiguous.

Example

Let’s say:

• String 1: "abcde"
• String 2: "ace"

The LCS is "ace" and its length is 3.

Why Use Dynamic Programming?

When solving LCS recursively, we may end up solving the same subproblems repeatedly. For instance, the same substring comparisons happen over and over again.

Dynamic Programming helps avoid this by:

• Breaking the problem into subproblems.
• Storing results of subproblems in a table (2D array).
• Building up the final solution using these stored results.

Step-by-Step Dynamic Programming Solution

Step 1: Create a 2D Table

Let dp[i][j] represent the length of the LCS of the first i characters of string 1 and first j characters of string 2.

• If either string is empty (i == 0 or j == 0), then dp[i][j] = 0.
• If s1[i-1] == s2[j-1], then the characters match. So, dp[i][j] = 1 + dp[i-1][j-1].
• If s1[i-1] != s2[j-1], we take the maximum LCS length by either excluding the current character from s1 or s2: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Step 2: Fill the Table

Use nested loops to fill the table starting from dp[0][0] to dp[m][n] where m and n are the lengths of s1 and s2.

Step 3: Final Answer

The value at dp[m][n] gives the length of the longest common subsequence.

Pseudocode

// Bottom-up 2D DP
function lcs(s1, s2):
    m = length of s1
    n = length of s2
    dp = 2D array of size (m+1) x (n+1)

    for i from 0 to m:
        for j from 0 to n:
            if i == 0 or j == 0:
                dp[i][j] = 0
            else if s1[i-1] == s2[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]

Trace Example

Let’s take s1 = "abcde", s2 = "ace"

i\j	""	a	c	e
""	0	0	0	0
a	0	1	1	1
b	0	1	1	1
c	0	1	2	2
d	0	1	2	2
e	0	1	2	3

Final result: dp[5][3] = 3 → LCS length = 3 (which is "ace")

Time and Space Complexity

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)

Dynamic Programming ensures that every subproblem (like comparing substrings of s1 and s2) is solved only once and reused. This drastically improves performance from exponential to polynomial time.

LCS is a classic DP problem and a stepping stone to many related problems like Shortest Common Supersequence, Longest Palindromic Subsequence, and Edit Distance.

---

Conclusion

Dynamic Programming is a versatile and powerful technique for solving optimization problems. By breaking problems into overlapping subproblems and using memoization or tabulation, DP ensures optimal and efficient solutions. It’s essential for problems involving sequences, paths, and decision making under constraints.