3753. Total Waviness of Numbers in Range II

class Solution {

    private String num;
    private long[][][][] memoCnt;
    private long[][][][] memoSum;

    public long totalWaviness(long num1, long num2) {
        return solve(num2) - solve(num1 - 1);
    }

    private long solve(long x) {
        if (x <= 0) return 0;

        num = String.valueOf(x);
        int n = num.length();

        memoCnt = new long[n + 1][11][11][20];
        memoSum = new long[n + 1][11][11][20];

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 11; j++) {
                for (int k = 0; k < 11; k++) {
                    Arrays.fill(memoCnt[i][j][k], -1);
                    Arrays.fill(memoSum[i][j][k], -1);
                }
            }
        }

        return dfs(0, 10, 10, 0, true)[1];
    }

    private long[] dfs(int pos, int prev1, int prev2,
                       int waviness, boolean tight) {

        if (pos == num.length()) {
            return new long[]{1, waviness};
        }

        if (!tight &&
            memoCnt[pos][prev1][prev2][waviness] != -1) {

            return new long[]{
                memoCnt[pos][prev1][prev2][waviness],
                memoSum[pos][prev1][prev2][waviness]
            };
        }

        int limit = tight ? num.charAt(pos) - '0' : 9;

        long count = 0;
        long sum = 0;

        for (int digit = 0; digit <= limit; digit++) {

            boolean nextTight = tight && (digit == limit);

            int nextWaviness = waviness;

            if (prev2 != 10 && prev1 != 10) {

                if ((prev1 > prev2 && prev1 > digit) ||
                    (prev1 < prev2 && prev1 < digit)) {
                    nextWaviness++;
                }
            }

            int nextPrev2 = prev1;
            int nextPrev1 = digit;

            if (prev1 == 10 && digit == 0) {
                nextPrev1 = 10;
                nextPrev2 = 10;
            }

            long[] res = dfs(
                pos + 1,
                nextPrev1,
                nextPrev2,
                nextWaviness,
                nextTight
            );

            count += res[0];
            sum += res[1];
        }

        if (!tight) {
            memoCnt[pos][prev1][prev2][waviness] = count;
            memoSum[pos][prev1][prev2][waviness] = sum;
        }

        return new long[]{count, sum};
    }
}

from functools import lru_cache

class Solution:
    def totalWaviness(self, num1: int, num2: int) -> int:

        def solve(x):
            if x <= 0:
                return 0

            s = str(x)

            @lru_cache(None)
            def dfs(pos, prev1, prev2, waviness, tight):

                if pos == len(s):
                    return (1, waviness)

                limit = int(s[pos]) if tight else 9

                cnt = 0
                total = 0

                for digit in range(limit + 1):

                    next_tight = tight and digit == limit
                    next_waviness = waviness

                    if prev2 != 10 and prev1 != 10:
                        if ((prev1 > prev2 and prev1 > digit) or
                            (prev1 < prev2 and prev1 < digit)):
                            next_waviness += 1

                    next_prev2 = prev1
                    next_prev1 = digit

                    if prev1 == 10 and digit == 0:
                        next_prev1 = 10
                        next_prev2 = 10

                    c, sm = dfs(
                        pos + 1,
                        next_prev1,
                        next_prev2,
                        next_waviness,
                        next_tight
                    )

                    cnt += c
                    total += sm

                return (cnt, total)

            return dfs(0, 10, 10, 0, True)[1]

        return solve(num2) - solve(num1 - 1)

class Solution {
    string num;
    long long memoCnt[20][11][11][20];
    long long memoSum[20][11][11][20];

public:

    long long totalWaviness(long long num1, long long num2) {
        return solve(num2) - solve(num1 - 1);
    }

private:

    long long solve(long long x) {

        if (x <= 0) return 0;

        num = to_string(x);

        memset(memoCnt, -1, sizeof(memoCnt));
        memset(memoSum, -1, sizeof(memoSum));

        return dfs(0,10,10,0,true).second;
    }

    pair<long long,long long> dfs(
        int pos,
        int prev1,
        int prev2,
        int waviness,
        bool tight
    ){

        if(pos==num.size())
            return {1,waviness};

        if(!tight && memoCnt[pos][prev1][prev2][waviness]!=-1)
            return {
                memoCnt[pos][prev1][prev2][waviness],
                memoSum[pos][prev1][prev2][waviness]
            };

        int limit=tight?num[pos]-'0':9;

        long long cnt=0,sum=0;

        for(int digit=0;digit<=limit;digit++){

            bool nextTight=tight && digit==limit;

            int nextWave=waviness;

            if(prev2!=10 && prev1!=10){
                if((prev1>prev2 && prev1>digit)||
                   (prev1<prev2 && prev1<digit))
                    nextWave++;
            }

            int np2=prev1;
            int np1=digit;

            if(prev1==10 && digit==0){
                np1=10;
                np2=10;
            }

            auto res=dfs(
                pos+1,
                np1,
                np2,
                nextWave,
                nextTight
            );

            cnt+=res.first;
            sum+=res.second;
        }

        if(!tight){
            memoCnt[pos][prev1][prev2][waviness]=cnt;
            memoSum[pos][prev1][prev2][waviness]=sum;
        }

        return {cnt,sum};
    }
};

var totalWaviness = function(num1, num2) {

    function solve(x) {

        if (x <= 0) return 0;

        const num = String(x);

        const memo = new Map();

        function dfs(pos, prev1, prev2, waviness, tight) {

            const key =
                pos + "|" +
                prev1 + "|" +
                prev2 + "|" +
                waviness + "|" +
                tight;

            if (!tight && memo.has(key))
                return memo.get(key);

            if (pos === num.length)
                return [1, waviness];

            const limit = tight ? Number(num[pos]) : 9;

            let count = 0;
            let sum = 0;

            for (let digit = 0; digit <= limit; digit++) {

                let nextWave = waviness;

                if (prev2 !== 10 && prev1 !== 10) {
                    if (
                        (prev1 > prev2 && prev1 > digit) ||
                        (prev1 < prev2 && prev1 < digit)
                    ) {
                        nextWave++;
                    }
                }

                let np1 = digit;
                let np2 = prev1;

                if (prev1 === 10 && digit === 0) {
                    np1 = 10;
                    np2 = 10;
                }

                const res = dfs(
                    pos + 1,
                    np1,
                    np2,
                    nextWave,
                    tight && digit === limit
                );

                count += res[0];
                sum += res[1];
            }

            const ans = [count, sum];

            if (!tight)
                memo.set(key, ans);

            return ans;
        }

        return dfs(0,10,10,0,true)[1];
    }

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