Dynamic Programming

0/1 Knapsack

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

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

Visualize this — step by stepNo signup needed.

The 0/1 Knapsack problem asks for the most valuable subset of items that fits a weight limit, where each item is taken whole or not at all. The DP state `dp[i][w]` is the best value using the first i items within weight w, and each cell is the better of two choices: skip item i, or take it and add its value to `dp[i-1][w - weight[i]]`.

It is the canonical introduction to two-dimensional DP, and the same take-or-skip shape appears in subset-sum, partition and countless contest problems.

The table is the algorithm. AlgoLens renders `dp` as a grid that fills in row by row, so you can trace any cell back to the two cells it came from.

The code

knapsack.cpp

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

int main() {
    vector<int> weight = {1, 3, 4, 5};
    vector<int> value  = {1, 4, 5, 7};
    int n = weight.size(), cap = 7;

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

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= cap; w++) {
            dp[i][w] = dp[i - 1][w];
            if (weight[i - 1] <= w) {
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight[i - 1]] + value[i - 1]);
            }
        }
    }

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

Open this in the visualizer

Now run your own 0/1 Knapsack

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.

Longest Common Subsequence

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

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.