Getting TLE for test case A = 75, B = 22

interview-questions
Tags: #<Tag:0x00007f2426995330>

#1

int dp[2005][2005];

int nds(int N, int S)
{
if(N < 1 || S < 1)
return 0;

if(N == 1 && S > 0 && S < 10)
    return 1;
    
if(dp[N][S] != -1)
    return dp[N][S];
    
for(int j = 0; j < S; j++)
{
    dp[N][S] = (dp[N][S]+nds(N-1, S-j))%1000000007;
    
}
return dp[N][S]+1;

}

int Solution::solve(int A, int B) {

memset(dp, -1, sizeof(dp));

int x = nds(A, B);
return x;

}