🗺️ Pathfinder Challenge
Find the minimum cost path from top-left to bottom-right
5x5
Start
Goal
Optimal Path
Obstacle
Coin
DP Table Visualization
Minimum Cost
-
Cells Computed
0
Time Complexity
O(n²)
Algorithm: Minimum Path Sum DP
// Recurrence Relation:
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
// Base Cases:
dp[0][0] = grid[0][0]
dp[i][0] = dp[i-1][0] + grid[i][0] // First column
dp[0][j] = dp[0][j-1] + grid[0][j] // First row🎒 Inventory Master
Select items to maximize value within weight capacity
20 kg
0 / 20 kg
Total Value: 0 💎
DP Table (Items × Capacity)
Max Value
-
Subproblems
0
Time Complexity
O(n×W)
Algorithm: 0/1 Knapsack DP
// Recurrence Relation:
dp[i][w] = max(
dp[i-1][w], // Don't take item i
dp[i-1][w-weight[i]] + value[i] // Take item i (if weight[i] <= w)
)
// Base Case:
dp[0][w] = 0 for all w
dp[i][0] = 0 for all i⚔️ Combat Strategist
Plan optimal attack sequences to defeat enemies efficiently
10 EP
🧙♂️
Hero
100/100 HP
10/10 EP
⚔️
👹
Goblin
50/50 HP
Available Skills
Battle ready! Compute optimal strategy...
Memoization Table (State → Optimal Damage)
Max Damage
-
States Cached
0
Cache Hits
0
Algorithm: Combat State Memoization
// State: (remaining_energy, cooldowns[])
// Memoization with state hashing
function maxDamage(energy, cooldowns, memo):
state = hash(energy, cooldowns)
if state in memo: return memo[state]
best = 0
for skill in available_skills:
if canUse(skill, energy, cooldowns):
newCooldowns = updateCooldowns(cooldowns, skill)
damage = skill.damage + maxDamage(energy - skill.cost, newCooldowns, memo)
best = max(best, damage)
memo[state] = best
return best📊 Performance Lab
Compare brute force vs dynamic programming algorithms
20
🐢 Brute Force
-
ms
Function Calls:
-
Time: O(2ⁿ)
⚡ Dynamic Programming
-
ms
Subproblems:
-
Time: O(n)
🚀 Speedup
-
times faster
Performance Comparison Chart
Recursive Call Tree (Brute Force)
Notice the overlapping subproblems highlighted in the same color