Dynamic programming in contests

Dynamic programming (from the Algorithms course) is everywhere in contests. Three patterns cover a great many problems.

Counting ways, modulo a prime

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

int main() {
    const long long MOD = 1000000007;
    int n = 10;
    vector<long long> ways(n + 1, 0);
    ways[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int step = 1; step <= 3; step++)
            if (i - step >= 0) ways[i] = (ways[i] + ways[i - step]) % MOD;
    }
    cout << "ways to climb " << n << " stairs: " << ways[n] << "\n";
    return 0;
}

"In how many ways can you climb n stairs taking 1, 2 or 3 steps at a time?" ways[i] = ways[i-1] + ways[i-2] + ways[i-3]. The counts grow exponentially, so problems ask for the answer modulo 10⁹ + 7: take % MOD after every addition, so the numbers stay small and never overflow long long.

The longest increasing subsequence

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

int main() {
    vector<int> a = {3, 10, 2, 1, 20, 4, 6, 7};
    int n = a.size();
    vector<int> best(n, 1);
    int answer = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (a[j] < a[i] && best[j] + 1 > best[i]) best[i] = best[j] + 1;
        if (best[i] > answer) answer = best[i];
    }
    cout << "longest increasing subsequence: " << answer << "\n";
    return 0;
}

best[i] is the length of the longest increasing subsequence that ends at a[i]: 1, plus the best best[j] over earlier j with a[j] < a[i]. The answer is the largest best[i]. This is O(n²); a cleverer version with binary search is O(n log n).

Knapsack in one row

The 0/1 knapsack's table needs only its previous row, so contests keep one array and loop the capacity downwards, so that each item is used at most once:

for (int i = 0; i < n; i++)
    for (int c = W; c >= w[i]; c--)
        best[c] = max(best[c], best[c - w[i]] + v[i]);

Mark lesson complete