🧩 Dynamic Programming Visualizer

Optimal substructure + overlapping subproblems → efficient solutions

Fibonacci Sequence

Problem: Compute F(n). Recurrence: F(n) = F(n−1) + F(n−2). Base: F(0)=0, F(1)=1.
Recurrence Relation
F(n) = F(n-1) + F(n-2)
Base: F(0) = 0, F(1) = 1
StatusReady

⚙️ Control

–Answer
–Cells
–O()

🔄 Step-by-Step DP Table Filling

Demo:
Ready
Select a problem and click Solve Step-by-Step.

📄 DP Code

Fibonacci – Tabulation

dp_fib.py


dp_fib.c






🧩 What is Dynamic Programming?


    

  1. Optimal substructure: Optimal solution builds from optimal sub-solutions.
    2. 

  2. Overlapping subproblems: Same subproblems recur in naive recursion.
    3. 

  3. Memoization (Top-down): Recursive + cache. Solve only needed subproblems.
    4. 

  4. Tabulation (Bottom-up): Iterative table fill from base cases.
    5. 

  5. Steps: Define state → write recurrence → set base cases → fill order → extract answer.
    6. 



🔝 Top-Down vs Bottom-Up
MemoizationTabulation
ApproachRecursive+cacheIterative+table
SubproblemsOnly neededAll computed
StackO(n) recursionNo stack
EaseNaturalNeed order


⏱️ Complexity
ProblemTimeSpace
FibonacciO(n)O(n)
0/1 KnapsackO(nW)O(nW)
LCSO(mn)O(mn)
Coin ChangeO(nA)O(A)


🎒 Classic DP Problems
0/1 Knapsack: Select items to maximize value within weight capacity.
LCS: Longest Common Subsequence of two strings.
Coin Change: Minimum coins to reach target amount.
Edit Distance: Min edits to transform one string to another.


💡 Problem-Solving Steps
1. Define state: what does dp[i] represent?
2. Recurrence: how to compute dp[i] from smaller?
3. Base cases: initial values.
4. Fill order: ensure dependencies come first.
5. Answer location in table.


🌍 Real-World Applications
Bioinformatics: DNA alignment (LCS, Edit Distance).
Finance: Portfolio optimization (Knapsack).
NLP: Viterbi algorithm, CYK parsing.
Routing: Shortest paths (Bellman-Ford = DP on graphs).