Dynamic Programming Visualization

Introduction to Dynamic Programming

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable when the subproblems overlap and have optimal substructure.

Key characteristics of Dynamic Programming problems:

Dynamic Programming uses two main approaches:

Top-Down (Memoization)

Start with the original problem and recursively break it down, storing results to avoid redundant calculations.

Advantages: Easier to implement, only calculates needed subproblems.

Bottom-Up (Tabulation)

Start with the smallest subproblems and build up to the original problem, typically using arrays or tables.

Advantages: More efficient, avoids recursion overhead, better space complexity.

Fibonacci Sequence
Longest Common Subsequence
Coin Change Problem

Fibonacci Sequence

The Fibonacci sequence is defined as: F(n) = F(n-1) + F(n-2) with base cases F(0) = 0 and F(1) = 1. This is a classic example demonstrating how dynamic programming improves efficiency over naive recursion.

Select a method and click the corresponding button to calculate the Fibonacci number.

Algorithm Comparison

Recursive (No DP)

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

Time Complexity: O(2ⁿ)

Space Complexity: O(n) for the call stack

Memoization (Top-Down)

function fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

Time Complexity: O(n)

Space Complexity: O(n)

Tabulation (Bottom-Up)

function fibonacci(n):
    if n <= 1:
        return n
    dp = array of size n+1
    dp[0] = 0, dp[1] = 1
    for i = 2 to n:
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Time Complexity: O(n)

Space Complexity: O(n)

Longest Common Subsequence (LCS)

The Longest Common Subsequence problem finds the longest subsequence common to two sequences. The subsequence must preserve the order of characters but need not be contiguous.

Enter two strings and click "Solve LCS" to find the longest common subsequence.

Algorithm Explanation

The dynamic programming approach for LCS:

  1. Create a table where cell [i][j] represents the length of LCS of the first i characters of String 1 and the first j characters of String 2.
  2. If the characters match: dp[i][j] = dp[i-1][j-1] + 1.
  3. If they don’t match: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
  4. The bottom-right cell contains the length of the LCS.
  5. Backtrack through the table to reconstruct the LCS.
function LCS(string1, string2):
    m = length of string1, n = length of string2
    dp = table of size (m+1) x (n+1) filled with 0
    for i = 1 to m:
        for j = 1 to n:
            if string1[i-1] == string2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    Backtrack to get LCS
    return dp[m][n] and the LCS

Time Complexity

O(m × n) - Where m and n are the lengths of the two strings

Space Complexity

O(m × n) - For the DP table

Coin Change Problem (DP Approach)

The Coin Change problem aims to find the minimum number of coins required to make a given amount. Dynamic Programming ensures an optimal solution regardless of the coin system.

Select a coin system and amount, then click "Solve with DP" to find the minimum number of coins.

Algorithm Explanation

The dynamic programming approach for the Coin Change problem:

  1. Create an array dp[] of size amount+1; initialize dp[0] = 0 and the rest to infinity.
  2. For each coin and each value from the coin’s value up to the target amount, update dp[value] if using the coin results in fewer coins.
  3. If dp[amount] remains infinity, no solution exists; otherwise, dp[amount] is the answer.
  4. Optionally, track the coins used to reconstruct the solution.
function coinChange(coins, amount):
    dp = array of size amount+1, initialize dp[0]=0 and dp[1...amount]=∞
    coinUsed = array of size amount+1, initialize all to -1
    for i = 1 to amount:
        for coin in coins:
            if i >= coin and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
                coinUsed[i] = coin
    if dp[amount] == ∞:
        return -1
    else:
        return dp[amount] and reconstruct the coins used

Time Complexity

O(amount × n) - Where n is the number of coin denominations

Space Complexity

O(amount) - For the DP array

DP vs. Greedy for Coin Change

For coins [1, 3, 4] and amount 6:

  • Greedy: 4, 1, 1 = 3 coins
  • DP: 3, 3 = 2 coins (optimal)

Dynamic Programming always finds the optimal solution.

Reconstructing the Solution

By tracking which coin was used for each amount, you can backtrack to show the coins that make up the optimal solution.

When to Use Dynamic Programming

Dynamic Programming is most effective when:

Common Dynamic Programming Problems