Stop Recomputing, Start Remembering Master Dynamic Programming From Knapsack to Tree DP & Digit DP — Identify States, Build Transitions, Optimize Space

Dynamic Programming (DP) is an optimization technique for problems that have two key properties: optimal substructure (the optimal solution to a problem can be built from optimal solutions of its subproblems) and overlapping subproblems (the same subproblems are solved repeatedly in a naive recursive solution).

Given n items with weights and values, and a knapsack of capacity W, choose a subset of items maximizing total value without exceeding W. Each item can be picked at most once (hence "0/1" — take it or leave it).

Tabulation (Bottom-Up)

def knapsack_tab(wt, val, W, n):
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            if wt[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], val[i-1] + dp[i-1][w-wt[i-1]])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

int knapsackTab(vector<int>& wt, vector<int>& val, int W, int n) {
    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (wt[i-1] <= w) {
                dp[i][w] = max(dp[i-1][w], val[i-1] + dp[i-1][w-wt[i-1]]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][W];
}

Same setup as 0/1 Knapsack, but now each item can be used unlimited times. This is the same pattern behind "Coin Change" and "Rod Cutting" problems.

def unbounded_knapsack(wt, val, W, n):
    dp = [0] * (W + 1)
    for w in range(1, W + 1):
        for i in range(n):
            if wt[i] <= w:
                dp[w] = max(dp[w], val[i] + dp[w - wt[i]])
    return dp[W]

int unboundedKnapsack(vector<int>& wt, vector<int>& val, int W, int n) {
    vector<int> dp(W+1, 0);
    for (int w = 1; w <= W; w++) {
        for (int i = 0; i < n; i++) {
            if (wt[i] <= w) {
                dp[w] = max(dp[w], val[i] + dp[w - wt[i]]);
            }
        }
    }
    return dp[W];
}

Given an array, find the length of the longest subsequence (not necessarily contiguous) where every element is strictly greater than the previous one.

import bisect
def lis_nlogn(arr):
    tails = []
    for num in arr:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

int lisNLogN(vector<int>& arr) {
    vector<int> tails;
    for (int num : arr) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    return tails.size();
}

Given two strings, find the length of their longest common subsequence. A subsequence is formed by deleting some characters without changing the order of remaining characters.

def longest_common_subsequence(text1, text2):
    n, m = len(text1), len(text2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                
    return dp[n][m]

int longestCommonSubsequence(string text1, text2) {
    int n = text1.length(), m = text2.length();
    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 (text1[i-1] == text2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[n][m];
}

Dynamic Programming on Trees involves traversing the tree (usually using DFS) and solving the subproblems defined at each node based on the solutions of its children.

Digit DP is used for problems that ask for the count or sum of numbers in a given range [L, R] that satisfy a specific property (e.g., sum of digits is a prime number).