Interactive DP Visualization
Fibonacci Sequence
Watch how dynamic programming efficiently computes Fibonacci numbers by storing and reusing previously calculated values.
Interactive Visualization:
Fibonacci Sequence: Each number is the sum of the two preceding ones, starting from 0 and 1. The sequence starts: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Time Complexity
- Recursive: O(2^n) - exponential growth
- Memoization: O(n) - linear time
- Tabulation: O(n) - linear time
Space Complexity
- Recursive: O(n) - call stack depth
- Memoization: O(n) - memo table + call stack
- Tabulation: O(n) - DP table
Step 0 of 0: Initial state
Knapsack Problem
See how dynamic programming solves the classic knapsack problem by building a table of optimal solutions for subproblems.
Interactive Visualization:
Knapsack Problem: Given a set of items, each with a weight and a value, determine which items to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Loading visualization...
Time Complexity
- Recursive: O(2^n) - exponential in the number of items
- Memoization: O(n*W) - where n is the number of items and W is the capacity
- Tabulation: O(n*W) - where n is the number of items and W is the capacity
Space Complexity
- Recursive: O(n) - call stack depth
- Memoization: O(n*W) - memo table + call stack
- Tabulation: O(n*W) - DP table
Step 0 of 0: Initial state
Longest Common Subsequence
Explore how dynamic programming finds the longest common subsequence between two strings by building a 2D table of solutions.
Interactive Visualization:
Longest Common Subsequence (LCS): The longest subsequence that appears in the same relative order in both strings, but not necessarily contiguous.
| i\j | 0 | B | D | C | A | B | A |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| D | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Time Complexity
- Recursive: O(2^(m+n)) - exponential in the length of the strings
- Memoization: O(m*n) - where m and n are the lengths of the strings
- Tabulation: O(m*n) - where m and n are the lengths of the strings
Space Complexity
- Recursive: O(m+n) - call stack depth
- Memoization: O(m*n) - memo table + call stack
- Tabulation: O(m*n) - DP table
Applications of LCS
- Diff Tools: Finding differences between files or versions
- DNA Sequence Alignment: Comparing genetic sequences
- Plagiarism Detection: Finding similarities between documents
- Version Control Systems: Merging changes from different branches
- Spell Checking: Suggesting corrections for misspelled words
Step 0 of 0: Initial state
Learning Objective
Visualize how dynamic programming works through interactive examples of classic DP problems, helping you understand the process of building solutions from subproblems.
Visualizing Dynamic Programming
Dynamic Programming can be easier to understand when you see it in action. These visualizations will help you grasp how DP builds solutions incrementally by solving and storing results of subproblems.
Fibonacci Sequence
Watch how DP efficiently computes Fibonacci numbers by storing and reusing previously calculated values.
Knapsack Problem
See how DP solves the classic knapsack problem by building a table of optimal solutions for subproblems.
Longest Common Subsequence
Explore how DP finds the longest common subsequence between two strings by building a 2D table of solutions.
Fibonacci Sequence
Watch how dynamic programming efficiently computes Fibonacci numbers by storing and reusing previously calculated values.
Interactive Visualization:
Fibonacci Sequence: Each number is the sum of the two preceding ones, starting from 0 and 1. The sequence starts: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Time Complexity
- Recursive: O(2^n) - exponential growth
- Memoization: O(n) - linear time
- Tabulation: O(n) - linear time
Space Complexity
- Recursive: O(n) - call stack depth
- Memoization: O(n) - memo table + call stack
- Tabulation: O(n) - DP table
Step 0 of 0: Initial state
How it works: This visualization compares the naive recursive approach with the DP approach. Notice how the recursive approach recalculates the same Fibonacci numbers multiple times, while the DP approach calculates each number only once and reuses the results.