Very simple bottom up solution using recursion and memoization


#1
int recur(vector<vector<int>>& dp, int N, int S, int i) {
if(S == 0) return 1;
if(i == N) return 0;

if(dp[i][S] != -1) return dp[i][S];

int m = 1000000007;
dp[i][S] = 0;

if(i != 0) dp[i][S] = recur(dp, N, S, i+1);  // take 0 only if it is not first digit
for(int j = 1; j < 10; ++j) {                       // take no. from 1 to 9
    if(S - j < 0) break;
    dp[i][S] = (dp[i][S] + recur(dp, N, S-j, i+1))%m;
}
return dp[i][S];

}
int Solution::solve(int N, int S) {
if(N == 0 || S == 0) return 0;
vector<vector> dp(N, vector(S+1, -1));
return recur(dp, N, S, 0);
}