2D DP: Knapsack and Longest Common Subsequence

0/1 knapsack

A bag holds at most W kg; each item has a weight and value; take it or leave it. dp[i][w] = best value using the first i items with capacity w: skip item i, or take it if it fits.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<pair<int, int>> items = {{1, 1}, {3, 4}, {4, 5}, {5, 7}};   // (weight, value)
    int W = 7, n = items.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++) {
        auto [weight, value] = items[i - 1];
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i - 1][w];                                       // skip
            if (weight <= w) dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + value);   // take
        }
    }
    cout << dp[n][W] << endl;
    return 0;
}

Output

9

Think of it like this: A 7 kg limit: the 3 kg item (value 4) plus the 4 kg item (value 5) beat the 5 kg item (7) plus the 1 kg item (1).

Longest common subsequence

A subsequence keeps order but may skip letters (“ace” is in “abcde”). dp[i][j] = LCS of the first i letters of a and first j of b:

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int lcs(const string& a, const string& b) {
    vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, 0));
    for (size_t i = 1; i <= a.size(); i++)
        for (size_t j = 1; j <= b.size(); j++)
            dp[i][j] = (a[i - 1] == b[j - 1]) ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
    return dp[a.size()][b.size()];
}

int main() {
    cout << lcs("abcde", "ace") << " " << lcs("AGGTAB", "GXTXAYB") << endl;
    return 0;
}

Output

3 4

Both are O(n × m). Tools like diff use the same idea.

Common mistake: Most DP bugs are off-by-one. An extra row and column for “zero items / empty string” keeps indexes simple.