Q2. DP2
predict the complexity of the code:
vector<vector > v(100,vector (100,-1) );
int func(int n,int m)
{
if((n==0)||(m==0))
{
return 0;
}
else
{
if(dp[m][n]!=-1)
{
return dp[m][n];
}
else
{ lli x;
int i;
for(i1;i<n;i++)
{
for(j=1;j<m;j++)
{
x=x+ func(n-i,m-j);
}
}
dp[m][n]=x;
return x;
}
}
}
O(n^3)
O(n^4)
O(2^n)
O(n^2)
@Akshita99, assuming dp is initialized with -1 , we are computing the function for state (n,m) only once as repetative cases are handled by memoization and for every state (n,m) we are running a doubly nested loop so for every state we will have N * M operations (for loops) and there are N * M unique states so overall operations is (N * M) * (N * M) which is closest to O(n^4)