Dynamic Programming — Algorithms

Dynamic Programming Visualizer

0/1 Knapsack

Étape 0 / 0

Speed 100ms

Step Progress 0 / 0

Table Size 0×0

Cells Filled 0

Status Ready

Uncomputed

Filling

Optimal path

0 / base case

Step Explanation

Select an algorithm and press Play to watch the table fill in.

—

Pseudocode

Dynamic Programming Algorithms

Dynamic Programming Algorithm Catalog

5 algorithms in this category. Click any card for detailed analysis.

Coin Change

Unstable

Coin Change (minimum coins) finds the fewest coins that sum to a target amount using an unlimited supply of given denominations. dp[i][a] is the minimum coins using the first i denominations to make amount a.

Ideal Use: For change-making, coin systems, and unbounded-knapsack-style resource problems.

Best

O(nA)

Worst

O(nA)

Space

O(nA)

Implementation Difficulty

★ ★ ☆ ☆ ☆ 2/5

Elementary

Graph algorithm — interactive visualization

Inspect & Visualize

0/1 Knapsack

Unstable

The 0/1 Knapsack problem asks: given items with weight and value, and a capacity, choose a subset that maximizes total value without exceeding the capacity. Each item is taken whole (0 or 1 times).

Ideal Use: Use for resource-allocation problems with indivisible items: budgeting, cargo loading, and subset-selection optimization.

Best

O(nW)

Worst

O(nW)

Space

O(nW)

Implementation Difficulty

★ ★ ★ ☆ ☆ 3/5

Intermediate

Graph algorithm — interactive visualization

Inspect & Visualize

Longest Common Subsequence

Unstable

The Longest Common Subsequence problem finds the longest sequence of characters that appears in the same order in two strings (but not necessarily contiguously). Used in diff tools, bioinformatics, and version control.

Ideal Use: For comparing sequences: file diffs, DNA/protein alignment, plagiarism detection, and edit-distance related problems.

Best

O(mn)

Worst

O(mn)

Space

O(mn)

Implementation Difficulty

★ ★ ★ ☆ ☆ 3/5

Intermediate

Graph algorithm — interactive visualization

Inspect & Visualize

Longest Increasing Subsequence

Unstable

The Longest Increasing Subsequence problem finds the longest subsequence of an array whose values are strictly increasing. The classic O(n²) DP tracks the length of the best increasing subsequence ending at each index.

Ideal Use: For sequencing and scheduling problems: longest chain, patience sorting, and box-stacking variants.

Best

O(n²)

Worst

O(n²)

Space

O(n)

Implementation Difficulty

★ ★ ★ ☆ ☆ 3/5

Intermediate

Graph algorithm — interactive visualization

Inspect & Visualize

Edit Distance (Levenshtein)

Unstable

Edit Distance (Levenshtein) measures how dissimilar two strings are by counting the minimum number of single-character edits — insertions, deletions, and substitutions — needed to turn one string into the other. dp[i][j] is the distance between the first i characters of a and the first j of b.

Ideal Use: Use for string similarity: spell checkers, DNA/protein sequence alignment, plagiarism detection, and fuzzy search ranking.

Best

O(mn)

Worst

O(mn)

Space

O(mn)

Implementation Difficulty

★ ★ ★ ☆ ☆ 3/5

Intermediate

Graph algorithm — interactive visualization

Inspect & Visualize

Dp Complexity Matrix

Complexity & Performance Tradeoffs

Side-by-side comparison of Big-O time and space complexity characteristics across dp algorithms.

Algorithm	Best Time	Average Time	Worst Time	Space Complexity	Stability
0/1 Knapsack	O(nW)	O(nW)	O(nW)	O(nW)	Unstable
Longest Common Subsequence	O(mn)	O(mn)	O(mn)	O(mn)	Unstable
Longest Increasing Subsequence	O(n²)	O(n²)	O(n²)	O(n)	Unstable
Coin Change	O(nA)	O(nA)	O(nA)	O(nA)	Unstable
Edit Distance (Levenshtein)	O(mn)	O(mn)	O(mn)	O(mn)	Unstable