C++ solution. Time Complexity O(N^2). Space Complexity O(N^2)


#1

#define mod 1000000007
int Solution::solve(int A, int B) {

//Base cases
if(B>A*9)
    return 0;
if(A==0)
    return 0;
    
//initiating DP
int dp[A+1][B+1];
for(int i = 0;i<A+1;i++){
    for(int j = 0;j<B+1;j++){
        dp[i][j] = 0;
    }
}
for(int i = 1;i<A+1;i++){
    dp[i][0] = 1;
}
for(int j = 1;j<=9 && j<B+1;j++){
    dp[1][j] = 1;
}
//Initialisation complete!

dp[0][0] = 0; //this is neccessary, but not required in this case as this case has already been dealt
for(int i = 2;i<A+1;i++){
    
    // First of all, update the above row... so that values starting with zeroes can be restored.
    for(int k = 1;k<B+1;k++){
        dp[i-1][k] += dp[i-2][k]%mod;
        dp[i-1][k] %= mod;
    }
    
    //main loop for updating current row
    for(int j = 1;j<B+1;j++){
        int k = j-1;
        while(k>=0 && k>j-10){
            dp[i][j]= (dp[i][j]%mod + dp[i-1][k]%mod)%mod;
            k--;
        }
    }
}
return dp[A][B]%mod;

}