#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3611
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	Radewoosh	3415
8	Um_nik	3376
9	maroonrk	3361
10	XVIII	3345

#	User	Contrib.
1	Qingyu	162
2	adamant	148
3	Um_nik	146
4	Dominater069	143
5	errorgorn	141
6	cry	138
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
10	soullless	133

Inspired by nor's blog (with permission). See comparison at the end of the post. And check his blog out. There's some interesting stuff on it :D

Disclaimer: You need C++17 for this to compile.

Introduction

When writing recursive DP, one usually need to save the result of a call (memoization) to prevent excessive computation. In python it's as easy as using a decorator:

from functools import cache
@cache
def fibo(n):
    return n if n <= 1 else fibo(n - 1) + fibo(n - 2)

In C++ you'd typically declare a multi-dimensional array, populate it with an unused constant, check if [x][y][z] has been calculated and finally store the result for later use. So much boilerplate... What if you could just paste a code snippet (from code editor or a file) and start solving the problem instead?

DP cache

Full snippet

template<class T, int N> struct mdvec {
    const array<int, N> ds;
    vector<T> v;
    mdvec(array<int, N> _ds) : ds(_ds) {
        int size = 1;
        for (int d : ds) size *= d;
        v.resize(size);
    }
    int index(const array<int, N> &ids) const {
        int id = 0, w = 1;
        for (int i = 0; i < N; i++) id += ids[i] * w, w *= ds[i];
        return id;
    }
    T &operator[](const array<int, N> &ids) { return v[index(ids)]; }
};

template<class R, int N, class F> struct Cache {
    mdvec<R, N> cache;
    mdvec<char, N> vis;
    F f;

    template<class T>
    Cache(array<int, N> ds, T &&_f) : cache(ds), vis(ds), f(forward<T>(_f)){};
    template<class... Ts> R operator()(Ts &&...xs) {
        if (vis[{xs...}]) return cache[{xs...}];
        return vis[{xs...}] = 1, cache[{xs...}] = f(*this, xs...);
    }
};
template<class R, int N, class F>
Cache<R, N, decay_t<F>> use_cache(array<int, N> ds, F &&f) { return {ds, forward<F>(f)}; }

Let's skip over the implementation details and talk about the interface and how to use it. All you should care about is:

use_cache<R, N>(array<int, N> ds, F f);

Where:

R is the type of the DP state.
N is how many dimensions you need to use.
ds specifies the size of each dimension in the internal N-D array.
f is a lambda with a function signature similar to (auto &self, int, char, bool, ...) -> R.

Example usage

Here's the code to count how many integers in the range $$$[1; n]$$$ have the sum of their digits divisible by $$$k$$$:

Code

using R = int64_t; // In case you need to change the return type, you only have to change it once here
int n, k;
vector<int> d = digits(n);
auto calc = use_cache<R, 3>(
    {n + 1, k, 2},
    [&](auto &f, int pos, int sum, bool tight) -> R {
        if (pos == d.size()) return sum == 0;
        int64_t total = 0;
        int lim = tight ? d[pos] : 9;
        for (int i = 0; i <= lim; i++)
            total += f(pos + 1, (sum + i) % k, i == lim && tight);
        return total;
    }
);
cout << calc(0, 0, 1) << "\n";