DSA Lab
Dynamic programming
Dynamic programming solves a problem by solving its smaller subproblems once each and storing their answers in a table, so each later answer is a quick combination of answers already known.
Dynamic programming: how it works
In this tool: lCS, knapsack, coin change. Put in your own values and watch it change. Each operation runs one step at a time and says in plain words what happened, with its calculation worked out. The code is shown in Python, C, C++ or Java with the line that just ran marked, and an Understand it panel gives the idea, why it works, the cost of each operation, common mistakes and a short quiz.
Lessons that use it
- Dynamic programming (Algorithms)Solve each subproblem once and store it: Fibonacci with a memo, and the fewest coins for any amount.
- Knapsack and longest common subsequence (Algorithms)Two classic 2D tables: the 0/1 knapsack (take or leave each item) and the LCS of two strings.
- Dynamic programming patterns (Interview Prep)Spot a DP problem, define the state and the recurrence, and solve it top-down with memoization or bottom-up with a table: climbing stairs, house robber, coin change and the longest increasing subsequence.
- Dynamic programming in contests (Competitive)Counting ways modulo 10⁹+7, the longest increasing subsequence, and the 1D knapsack: the DP patterns that keep coming back.