ProgramGuru.org

ProgramGuru.org

Dynamic Programming Technique in DSA

Dynamic Programming in a Nutshell

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:

Top-Down vs Bottom-Up Approach

Example 1: Fibonacci Number — Explained for Beginners

Problem Statement:

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

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:

Space Complexity:

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:

Space Complexity:

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.

Example 2: 0/1 Knapsack Problem

Problem: You are given:

Your goal is to choose a subset of these items such that:

Why Dynamic Programming?

This problem has two important properties:

Hence, Dynamic Programming (DP) is the ideal approach. We’ll use Bottom-Up DP (Tabulation) where we fill a 2D table dp[i][w] representing:

Step-by-Step Explanation

  1. Create a DP Table: Build a 2D table with dimensions (n+1) x (W+1).
  2. Base Case Initialization:
    • dp[0][w] = 0 → 0 items, so 0 value.
    • dp[i][0] = 0 → 0 capacity, so 0 value.
  3. Fill the Table:
    • Loop through each item (1 to n).
    • Loop through each capacity (1 to W).
    • For each dp[i][w] we ask:
      • Can I include item i-1? Check if weight[i-1] ≤ w.
      • If yes, then consider both:
        • Include it → value becomes value[i-1] + dp[i-1][w - weight[i-1]].
        • Exclude it → value is just dp[i-1][w].
      • Choose the maximum of these two options.
      • If item can’t be included, just copy the value from above row.
  4. Final Answer: The cell dp[n][W] contains the max value for the full problem.

Visual Representation of Table Update

Imagine the following small example:

The table dp[i][w] gets filled row by row. Each cell compares two options: take or skip the item.

Pseudocode (Bottom-Up Approach)

// 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]

Time and Space Complexity

Takeaway

Dynamic Programming helps solve the 0/1 Knapsack problem by:

This avoids exponential time from trying all subsets (which is what brute force would do), and gives an efficient solution.

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:

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:

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.

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""ace
""0000
a0111
b0111
c0122
d0122
e0123

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

Time and Space Complexity

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.

Advantages and Disadvantages of DP

Advantages

Disadvantages

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.