Hey , I see that my code passed different samples but it still TLE
here is my code
#include <bits/stdc++.h>
using namespace std;
int x;
char s[5001];
int64_t ar[5000*5000];
void inill ()
{
for (int i = 0 ; i < 5000 * 5000; i++)
{
ar[i] = -1;
}
}
int64_t dp (string ss, int dex)
{
if (dex <= x-1)
{
if (ss.size() == 2)
{
if (ss[0] == ‘0’) return 0;
if ((ss[0] - ‘0’) * 10 + (ss[1] -‘0’) > 26 || (ss[0] - ‘0’) * 10 + (ss[1] -‘0’) == 0) {return 0;}
if (dex == x - 1) return 1;
}
else
{
if (ss[0] == ‘0’) return 0;
if (dex == x - 1) return 1;
}
ss = “”;
ss += s[dex + 1];
if (ar[dex] != -1) return ar[dex];
return ar[dex] = dp(ss , dex + 1) + dp(ss + s[dex + 2] , dex + 2);
}
else return 0;}
int main()
{
while (cin.getline(s , 5001))
{
x = strlen(s);
string ss = “”;
ss += s[0];
if (s[0] == ‘0’) break;
inill();
cout << dp(ss, 0) + dp(ss + s[1], 1) << endl;
}
}