Dynamic Programming

Longest Common Subsequence

How much two strings share, in order — the basis of diff.

TimeO(n·m)SpaceO(n·m)CategoryDynamic Programming

Visualize this — step by stepNo signup needed.

The LCS of two strings is the longest sequence of characters appearing in both, in the same order but not necessarily contiguously. `dp[i][j]` holds the LCS length of the first i and first j characters: on a character match it extends the diagonal cell by one, otherwise it takes the better of dropping one character from either string.

This is what `git diff` computes, and it underlies edit distance, DNA sequence alignment and plagiarism detection.

The diagonal-versus-neighbour choice is much easier to see than to read. AlgoLens draws `dp` as a grid, so each cell visibly depends on the three around it.

The code

longest_common_subsequence.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s = "ABCBDAB", t = "BDCABA";
    int n = s.size(), m = t.size();

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    cout << dp[n][m] << '\n';
    return 0;
}

Open this in the visualizer

Now run your own Longest Common Subsequence

AlgoLens traces your code — arrays, graphs, trees and recursion — from a real execution, so you see how it actually behaves, not a canned animation.

Paste your code

Keep going

Fibonacci with Memoization

Turn exponential recursion into linear time by caching subresults.

0/1 Knapsack

Take it or leave it — the DP table that defines the field.

Coin Change

Fewest coins for an amount — where greedy fails and DP works.

Bubble Sort

The simplest sort — watch the largest value bubble to the end each pass.