0/1 Knapsack
Optimize item selection to maximize total profit under weight constraints.
Coin Change
Find min coins or total combinations to make a target amount.
LCS Subsequence
Determine the longest subsequence shared across two string inputs.
LIS Sequence
Identify the longest strictly increasing subsequence in an array.
Edit Distance
Determine min edits to align strings using insert, delete, and replace.
Matrix Chain Multiplication
Find optimal product ordering to minimize scalar multiplication operations.
Subset Sum Solver
Verify if elements can sum up exactly to a target sum.
Rod Cutting Solver
Evaluate best pieces cuts to maximize selling profit values.
Partition Problem
Determine if elements can be split into two equal-sum subsets.
Memoization Playground
Trace recursive stack flows and check cache hit lookups.
Tabulation Playground
Monitor bottom-up table updates and loop iterations.
Space Optimization
Compare memory footprints of original 2D grids vs optimized 1D rows.
Digit DP Studio
Count satisfying number ranges. (Coming Soon)
Tree DP Studio
Compute subtree constraints recursively using DFS. (Coming Soon)
Bitmask DP Studio
Solve state permutations using binary bit integer masks. (Coming Soon)
Travelling Salesman
Solve minimum cost Hamiltonian tours. (Coming Soon)
Dynamic Programming Foundations
Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting:
- Overlapping Subproblems: Subproblems are solved repeatedly.
- Optimal Substructure: Optimal solutions to subproblems build the global optimum.
Top-Down vs Bottom-Up
Choose your strategy depending on constraints:
- Memoization (Top-Down): Natural recursion, computes only necessary reachable states.
- Tabulation (Bottom-Up): Iterative tables loop sweeps, avoids recursion stack limits and enables space-optimization.