N digit numbers with digit sum S

• Time : $O(AB)$
• Space : $O(AB)$

const long long mod = 1e9 + 7;
long long helper(vector<vector<long long>>& dp, int n, int sum) {
    if(n < 0) return sum == 0;
    if(sum < 0) return 0;
    if(dp[n][sum] != -1) return dp[n][sum];
    long long& res = dp[n][sum] = 0;
    for(int i = 0; i <= min(9,sum); i++) {
        res = (res + helper(dp, n - 1, sum - i)) % mod;
    }
    return res;
}
int Solution::solve(int A, int B) {
    vector<vector<long long>> dp(A, vector<long long>(B, -1));
    long long res = 0;
    for(int i = 1; i <= min(9,B); i++) {
        res = (res + helper(dp, A - 2, B - i)) % mod;
    }
    return res;
}