### rum3r's blog

By rum3r, history, 5 weeks ago,

Can anyone tell me why I am getting TLE with this Top Down Recursive (Rectangle Cutting CSES) and also Runtime Error. Thought I have memoized the results. Is the time complexity still more than O(a^2*b + a*b^2). I know you may ask why top down. I am just trying to explore possible ways. Code--

int solve(vector<vector<int>> dp, int l, int b){
if(l == b){
return 0;
}
if(l==0 || b==0){
return 0;
}
if(dp[l][b] != inf){
return dp[l][b];
}
for(int k=1; k<l; ++k){
dp[l][b] = min(dp[l][b], 1+solve(dp, k, b)+solve(dp, l-k, b));
}
for(int k=1; k<b; ++k){
dp[l][b] = min(dp[l][b], 1+solve(dp, l, k)+solve(dp, l, b-k));
}
return dp[l][b];
}


ANY HELP WOULD BE APPRECIATED!! PEACE!!

• -1

 » 5 weeks ago, # |   0 Either pass DP array by reference or declare it globally. Every single time you call solve() a new copy of DP array is created resulting in tle.
•  » » 5 weeks ago, # ^ |   0 Thanks!
 » 5 weeks ago, # |   0 First of all you should pass dp as reference, but even then I think you will end up with a TLE. $O(500^3)$ along with the overhead complexity of calling functions might not fit into time limit. When the time limit is tight you should always opt for bottom up rather than top down.
•  » » 5 weeks ago, # ^ |   0 Thanks! I know that bottom up approach is good for dp but I was just exploring. How to implement it using top down. Even though complexity is same as bottom up. But it was still getting TLE. You cleared my doubt:)
•  » » 5 weeks ago, # ^ |   0 Yes, Bro it gets TLE in two tc's