Easy C++ backtracking using Memoization


#1

long int dp[1000][1000];
long int helper(int i, int n, int s) {
if (s < 0 || (i == n + 1 && s > 0) || (i == n && s > 9))
return 0;
if ((i == n + 1 && s == 0) || (i == n && s <= 9))
return 1;
if (dp[i][s] != -1)
return dp[i][s];
long int x = 0, z = 0;
if (i == 1)
z = 1;
for (int j = z; j <= 9; j++)
x = (x + helper(i + 1, n, s - j)) % 1000000007;
return dp[i][s] = x;
}
int Solution::solve(int A, int B) {
memset(dp, -1, sizeof(dp));
return helper(1, A, B);
}