Dynamic Programming in C++

Dynamic programming (DP) solves problems made of overlapping sub-problems by solving each sub-problem once and storing its answer. It turns exponential brute force into polynomial time, and it's the most feared – and most rewarded – topic in coding interviews. The trick is a repeatable method, shown here with the STL's vectors.

From recursion to DP

#include <iostream>
#include <vector>

long long calls = 0;
long long fib_naive(int n) { calls++; return n < 2 ? n : fib_naive(n - 1) + fib_naive(n - 2); }

std::vector<long long> memo(91, -1);
long long fib_memo(int n) {                     // top-down: recursion + cache
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
}

long long fib_table(int n) {                    // bottom-up: fill a table in order
    std::vector<long long> dp(n + 1);
    dp[0] = 0;
    if (n > 0) dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

int main() {
    std::cout << fib_naive(30) << " using " << calls << " calls\n";
    std::cout << fib_memo(90) << '\n' << fib_table(90) << '\n';
    return 0;
}

832040 using 2692537 calls
2880067194370816120
2880067194370816120

Coin change

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> coins{1, 5, 6, 9};
    int amount = 11;
    std::vector<int> dp(amount + 1, INT_MAX);         // dp[a] = fewest coins to make a
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a && dp[a - c] != INT_MAX) dp[a] = std::min(dp[a], dp[a - c] + 1);
    std::cout << "fewest coins for " << amount << ": " << dp[amount] << '\n';

    std::vector<long long> ways(amount + 1, 0);       // number of ways (order doesn't matter)
    ways[0] = 1;
    for (int c : coins)                               // coins outer: each combination counted once
        for (int a = c; a <= amount; a++) ways[a] += ways[a - c];
    std::cout << "ways to make " << amount << ": " << ways[amount] << '\n';
    return 0;
}

fewest coins for 11: 2
ways to make 11: 6

A greedy "take the biggest coin" approach gives 9 + 1 + 1 = 3 coins for 11, but DP finds 5 + 6 = 2. That's why DP is needed when greedy choices can be wrong.

0/1 knapsack

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> weight{1, 3, 4, 5}, value{15, 50, 60, 90};
    int capacity = 8;
    std::vector<int> dp(capacity + 1, 0);               // dp[w] = best value with capacity w
    for (std::size_t i = 0; i < weight.size(); i++)
        for (int w = capacity; w >= weight[i]; w--)       // backwards: each item used at most once
            dp[w] = std::max(dp[w], dp[w - weight[i]] + value[i]);
    std::cout << "best value: " << dp[capacity] << '\n';
    return 0;
}

best value: 140

The 2D version dp[i][w] ("best value using the first i items and capacity w") is easier to read; looping capacity backwards lets one 1D array do the same job in O(W) memory.

Longest increasing subsequence with lower_bound

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> a{10, 9, 2, 5, 3, 7, 101, 18, 4, 20};
    std::vector<int> tails;                       // tails[k] = smallest tail of an increasing run of length k+1
    for (int x : a) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);   // extends the longest run
        else *it = x;                                // a better (smaller) tail for that length
    }
    std::cout << "LIS length: " << tails.size() << '\n';
    return 0;
}

LIS length: 5

The classic DP for LIS is O(n²); keeping the smallest possible tail for each length and binary-searching with lower_bound makes it O(n log n) – a favourite interview follow-up.

Modular arithmetic

Counting problems often say "print the answer modulo 10⁹ + 7", because the true count is astronomically large:

#include <iostream>
#include <vector>

constexpr long long MOD = 1'000'000'007;

long long power_mod(long long base, long long exp) {
    long long result = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

int main() {
    int n = 1000;                               // ways to climb n stairs taking 1 or 2 steps
    std::vector<long long> dp(n + 1);
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++) dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;   // reduce at every step
    std::cout << dp[n] << '\n';
    std::cout << power_mod(2, 1'000'000) << '\n';
    return 0;
}

107579939
235042059

Practice

Summary

Interview practice: dynamic programming questions.