What is my code's Time complexity?
akhilvaid21
71

Hi everyone,

I'm trying to solve this question : https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/

My code is :

unordered_map<int,unordered_map<int,int>> dp;
    int solver(int d, int f, int target)
    {
        
        if(target<=f )
            return 1;
        if(d<=1)
            return 0;
        
        if(dp[d][target]>0)
            return dp[d][target];
        int ans = 0;
        for( int i=1 ; i<=f ; i++)
        {
            ans+= solver(d-1, f, target-i)%mod;
            
        }
        dp[d][target]  = ans;
        return (ans);
        
        
    }
    
    int numRollsToTarget(int d, int f, int target) {
        return solver(d,f,target)%mod;
    }

But my code fails on testcase :

30
30
500

The accepted code is :

int dp[31][1001] = {};

int numRollsToTarget(int d, int f, int target, int res = 0) {

if (d == 0 || target <= 0) return d == target;
  if (dp[d][target]) return dp[d][target] - 1;
  
  for (auto i = 1; i <= f; ++i)
    res = (res + numRollsToTarget(d - 1, f, target - i)) % 1000000007;

dp[d][target] = res + 1;
  return res;
}

How is my code giving TLE when it is exactly similiar to the accepted code? Am I missing something?
Thanks.

Comments (1)