Count Evenly Good Integers solution and explanation

class Solution:
    def countEvenlyGoodIntegers(self, l: int, r: int) -> int:
        @cache
        def dfs(pos: int, st: int, lim: bool) -> int:
            if pos >= len(s):
                return st ^ 1
            up = int(s[pos]) if lim else 9
            return sum(
                dfs(pos + 1, (st + (i & 1 ^ 1)) % 2, lim and i == up)
                for i in range(up + 1)
            )

        s = str(l - 1)
        a = dfs(0, 0, True)
        dfs.cache_clear()
        s = str(r)
        b = dfs(0, 0, True)
        return b - a

class Solution {
    String s;
    long[][][] f;

    public long countEvenlyGoodIntegers(long l, long r) {
        return calc(r) - calc(l - 1);
    }

    private long calc(long x) {
        s = String.valueOf(x);
        f = new long[s.length()][2][2];
        for (long[][] a : f) {
            for (long[] b : a) {
                Arrays.fill(b, -1);
            }
        }
        return dfs(0, 0, true);
    }

    private long dfs(int pos, int st, boolean lim) {
        if (pos >= s.length()) {
            return st ^ 1;
        }
        int k = lim ? 1 : 0;
        if (f[pos][st][k] != -1) {
            return f[pos][st][k];
        }
        int up = lim ? s.charAt(pos) - '0' : 9;
        long res = 0;
        for (int i = 0; i <= up; ++i) {
            res += dfs(pos + 1, (st + (i & 1 ^ 1)) % 2, lim && i == up);
        }
        return f[pos][st][k] = res;
    }
}

class Solution {
    string s;
    long long f[20][2][2];

    long long dfs(int pos, int st, bool lim) {
        if (pos >= s.size()) {
            return st ^ 1;
        }
        if (f[pos][st][lim] != -1) {
            return f[pos][st][lim];
        }
        int up = lim ? s[pos] - '0' : 9;
        long long res = 0;
        for (int i = 0; i <= up; ++i) {
            res += dfs(pos + 1, (st + (i & 1 ^ 1)) % 2, lim && i == up);
        }
        return f[pos][st][lim] = res;
    }

    long long calc(long long x) {
        s = to_string(x);
        memset(f, -1, sizeof(f));
        return dfs(0, 0, true);
    }

public:
    long long countEvenlyGoodIntegers(long long l, long long r) {
        return calc(r) - calc(l - 1);
    }
};

function countEvenlyGoodIntegers(l: number, r: number): number {
    let s: string;
    let f: number[][][];

    const calc = (x: number): number => {
        s = String(x);
        f = Array.from({ length: s.length }, () =>
            Array.from({ length: 2 }, () => Array(2).fill(-1)),
        );

        const dfs = (pos: number, st: number, lim: boolean): number => {
            if (pos >= s.length) {
                return st ^ 1;
            }
            const k = lim ? 1 : 0;
            if (f[pos][st][k] !== -1) {
                return f[pos][st][k];
            }
            const up = lim ? Number(s[pos]) : 9;
            let res = 0;
            for (let i = 0; i <= up; ++i) {
                res += dfs(pos + 1, (st + ((i & 1) ^ 1)) % 2, lim && i === up);
            }
            return (f[pos][st][k] = res);
        };

        return dfs(0, 0, true);
    };

    return calc(r) - calc(l - 1);
}

func countEvenlyGoodIntegers(l int64, r int64) int64 {
	var s string
	var f [20][2][2]int64

	calc := func(x int64) int64 {
		s = strconv.FormatInt(x, 10)
		for i := range f {
			for j := range f[i] {
				for k := range f[i][j] {
					f[i][j][k] = -1
				}
			}
		}

		var dfs func(pos, st int, lim bool) int64
		dfs = func(pos, st int, lim bool) int64 {
			if pos >= len(s) {
				return int64(st ^ 1)
			}
			k := 0
			if lim {
				k = 1
			}
			if f[pos][st][k] != -1 {
				return f[pos][st][k]
			}
			up := 9
			if lim {
				up = int(s[pos] - '0')
			}
			var res int64
			for i := 0; i <= up; i++ {
				res += dfs(pos+1, (st+(i&1^1))%2, lim && i == up)
			}
			f[pos][st][k] = res
			return res
		}

		return dfs(0, 0, true)
	}

	return calc(r) - calc(l-1)
}