#include <iostream>
#include <map>
#include <tuple>

int WeightImpl(int i, int q, int d); // forward declaration

// Use memoization and use `WeightImpl` for the real computation
int Weight(int i, int q, int d){
    static std::map<std::tuple<int, int, int>, int> memo;

    auto it = memo.find(std::make_tuple(i, q, d));
    if (it != memo.end()) {
        return it->second;
    }
    const int res = WeightImpl(i, q, d);
    memo[std::make_tuple(i, q, d)] = res;
    return res;
}

// Do the real computation
int WeightImpl(int i, int q, int d){
    int j, sum = 0;
    if (i <= 0)
        return 0;
    else if (i == 1)
        return 1;
    for (j = 1; j <= d; j++){
        sum += Weight((i - j), q, d); // Call the memoize version to save intermediate result
    }
    sum = 1 + ((q - 1) * sum);
    return sum;
}

int main() {
	std::cout << Weight(6, 5, 3) << std::endl;
}