CPCRC1C – Sum of Digits – SPOJ

#include <iostream>
#include <cstring>
#define ll long long
using namespace std;

ll a, b;
string n;
ll memo[10][2][90];

ll dp(ll position, bool tight, ll sum) {
    if (position == n.length()) {
        return sum;
    }

    if (memo[position][tight][sum] != -1) {
        return memo[position][tight][sum];
    }

    ll limit = tight ? n[position] - '0' : 9;
    ll result = 0;
    for (int digit = 0; digit <= limit; ++digit) {
        bool newTight = tight && digit == limit;
        result += dp(position + 1, newTight, sum + digit);
    }

    return memo[position][tight][sum] = result;
}

ll sumDigits(ll x) {
    n = to_string(x);
    memset(memo, -1, sizeof(memo));
    return dp(0, true, 0);
}

int main() {
    while (true) {
        cin >> a >> b;
        if (a == -1 && b == -1) {
            break;
        }
        cout << sumDigits(b) - sumDigits(a - 1) << endl;
    }

    return 0;
}