定义吉利数为数位上相邻两位之和不是4，且每一位不是4，求 $[L,R]$ 吉利数的个数，多组测试数据。 $T<5\times 10^5,L,R<10^{18}$

我写了记忆化搜索版的数位dp,但是不知为何超时。

#include<bits/stdc++.h>
#define int long long

using namespace std;

int a[20], p[20][10][2];

int dfs (int at, int last, bool is) {
	if (!at)  return 1;
	
	if (p[at][last][is] != -1)  return p[at][last][is];
	
	int ans = 0, maxn = (is ? a[at] : 9);
	
	for(int i = 0; i <= maxn; ++ i)
		if((i != 4) && (i + last != 4))
			ans += dfs (at - 1, i, is && (i == maxn));
			
	return p[at][last][is] = ans;
}

int dp (int n) {
	memset(a, 0, sizeof(a));
	memset(p, -1, sizeof(p));
	
	int cnt = 0;
	
	while (n) {
		a[ ++ cnt] = n % 10;
		n /= 10;
	}
	
	return dfs(cnt,0,1);
}

signed main() {
	int T;
	
	scanf("%lld",&T);
	
	while (T -- ) {
		int l, r;
		
		scanf("%lld%lld", &l, &r);
		
	    printf("%lld\n",dp(r) - dp(l - 1));
	}
	
	return 0;
}