dp_digits

using ll = long long;
class Solution {

public:
    ll dp[20][2][2][11][11];
    string s1, s2;
    string s;
    int n;
    ll digit(ll i, bool f, bool started, int prev1, int prev2) {
        if (i == n)
            return 0;
        ll& ret = dp[i][f][started][prev1 + 1][prev2 + 1];
        if (ret != -1)
            return ret;
        ll res = 0;
        ll R = f ? 9 : (s[i] - '0');

        for (int dgt = 0; dgt <= R; dgt++) {

            bool nf = f || (dgt < (s[i] - '0'));
            bool nstar = started || (dgt != 0);
            int add = 0;
            int np1, np2;
            if (!nstar) {
                np1 = -1, np2 = -1;
            } else if (!started && nstar) {
                np1 = -1;
                np2 = dgt;
            } else {
                np1 = prev2;
                np2 = dgt;
                if (prev1 != -1 && prev2 != -1 && nstar) {
                    if ((prev1 < prev2 && prev2 > dgt) ||
                        (prev1 > prev2 && prev2 < dgt))
                        add = 1;
                }
            }

            res += add + digit(i + 1, nf, nstar, np1, np2);
        }
        return ret = res;
    }

    ll calc(ll x) {
        if (x <= 0)
            return 0;
        s = to_string(x);
        n = s.size();
        memset(dp, -1, sizeof(dp));
        return digit(0, 0, 0, -1, -1);
    }
    long long totalWaviness(long long num1, long long num2) {

        return calc(num2) - calc(num1 - 1);
    }
};