Dice Rolls

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

long long dp[1010101], mod = 1e9 + 7;
long long helper(int k) {
    if(k < 0) return 0;
    long long& res = dp[k];
    if(res != -1) return res;
    res = 0;
    for(int i = 1; i <= 6; i++) res = (res + helper(k-i)) % mod;
    return res;
}
int Solution::solve(int A) {
    memset(dp,-1,sizeof dp);
    dp[0] = 1;
    return helper(A);
}