[C++] Why are Global Vectors giving TLE?
DammitWA
354
Array

While using vector<int> dp globally for memoization. The written code throws TLE. However, if I replace that dp with arrays, like int dp[100] the same code is accepted with huge time difference.

Can someone explain why does it happen?

I am pasting both the accepted and the rejected code for references:

Code 1 (TLE):

vector<vector<vector<int>>> dp;

int rec(int n , int notepad , int copy , int have_copied = false){
	if(notepad > n || copy > n) return 1e8;
	if(notepad == n) return 0;

	if(dp[notepad][copy][have_copied] != -1) return dp[notepad][copy][have_copied];

	int case1 = 1 + rec(n , notepad + copy , copy , false); //have_copied = false, since now we have something new to copy

	int case2 = 1e8;
	if(!have_copied){
		//since we don't want to copy something that was already copied
		case2 = 1 + rec(n , notepad , notepad , true);
	}
	return dp[notepad][copy][have_copied] = min(case1 , case2);
}

Code 2 (Accepted)

int dp[1001][1001][2];

int rec(int n , int notepad , int copy , int have_copied = false){
	if(notepad > n || copy > n) return 1e8;
	if(notepad == n) return 0;

	if(dp[notepad][copy][have_copied] != -1) return dp[notepad][copy][have_copied];

	int case1 = 1 + rec(n , notepad + copy , copy , false); //have_copied = false, since now we have something new to copy

	int case2 = 1e8;
	if(!have_copied){
		//since we don't want to copy something that was already copied
		case2 = 1 + rec(n , notepad , notepad , true);
	}
	return dp[notepad][copy][have_copied] = min(case1 , case2);
}
Comments (1)