I'm stuck with a contest problem.
Description:
What is the minimum number of moves to annihilate an int array where the possible moves are:
- Remove both the first and last elements if they are equal to each other, or
- Remove the first element, or
- Remove the last element.
Input
The first line is the number of test cases (less than or equal to 200).
For any test case there is two lines.
- Line 1 has 1 integer with the size of the vector. (The size never exceeds 1000)
- Line 2 has n integers with the values of the vector. (Values never greater than 109)
Ouput
The output must show the test case number with the minimum value of remove steps.
Input Example:
3
5
1 3 1 3 2
5
1 2 3 2 1
7
1 1 2 3 3 4 2
Output Example:
Case #1: 4
Case #2: 3
Case #3: 5
My solution is brute-force and recursive, with memorization:
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int minOf2(int x, int y){
return (x < y) ? x : y;
}
int minOf3(int x, int y, int z){
return minOf2(z,minOf2(x,y));
}
int memoization[1010][1010];
int recur(unsigned long long *arr,int i,int j){
if(i > j){
return 0;
}
int aux = INT_MAX;
if(arr[i] == arr[j]){
aux = recur(arr,i+1,j-1);
}
if(memoization[i][j])
return memoization[i][j];
else
return memoization[i][j] = 1 + minOf3(aux,recur(arr,i+1,j),recur(arr,i,j-1));
}
int main()
{
int t,n,i,j;
unsigned long long arr[1010];
scanf("%d",&t);
for (i = 1; i <= t; i++) {
memset(memoization,0,sizeof(memoization));
scanf("%d",&n);
for (j = 0; j < n; j++) {
scanf("%llu",&arr[j]);
}
printf("Case #%d: %d\n",i,recur(arr, 0, n-1));
}
return 0;
}
This solution is still getting "Time Limit Exceeded".