Other algorithms / interactive lesson
Learn dynamic programming through three different problems at once: Fibonacci, longest increasing subsequence, and 0/1 knapsack. Watch states, recurrences, comparisons, and backtracking inside an animated DP table.
About the algorithm
Dynamic programming solves a problem by breaking it into overlapping subproblems, storing the answer of each subproblem, and then building the final solution from those stored answers. This lesson uses three classic examples: Fibonacci, longest increasing subsequence, and 0/1 knapsack.
Richard Bellman popularized the term dynamic programming in the 1950s while working on multistage decision processes. Since then, dynamic programming has become one of the core design techniques in algorithms, optimization, operations research, and computer science education.
A dynamic-programming solution begins by defining a state, such as a table cell, that captures one subproblem. Next, it defines a recurrence describing how that state depends on smaller states. Finally, it fills the table in an order that guarantees each dependency is already known. Some problems, such as LIS or knapsack, also store backtracking information so the actual optimum solution can be reconstructed after the table is full.
Dynamic programming appears everywhere: sequence analysis, shortest paths, edit distance, knapsack-like planning, bioinformatics, compiler optimization, scheduling, finance, and game theory. Whenever a problem combines optimal substructure with overlapping subproblems, dynamic programming is a strong candidate.
Code companion
Connect each visual decision to an implementation pattern.
choose a state definition
choose base cases
choose a recurrence
fill the table in dependency order
if needed, backtrack from the optimum cell to recover the actual solution
example: 0/1 knapsack
for w from 0 to capacity:
dp[0][w] = 0
for i from 1 to n:
for w from 0 to capacity:
if item[i].weight > w:
dp[i][w] = dp[i - 1][w]
else:
dp[i][w] = max(
dp[i - 1][w],
dp[i - 1][w - item[i].weight] + item[i].value
)