I came across this problem, and thought to myself; this is classical DP that can be solved with memoization, specially when I saw that N <= 100.

But I got wrong answer on test 6.And when I read the editorial, it mentionned another way entirely.(solving the opposite problem -_-)

So my question is, why didn't the brute for this one work?

Here is my code:

int dp[110][110];
 
int solve(int* A,int N,int i,int prev,int nbr){
	if(i == N) return 0;
	
	if(dp[i][nbr] != -1) return dp[i][nbr];
	
	if(A[i] == 0) return dp[i][nbr] = 1 + solve(A,N,i+1,0,nbr+1);
	
	else if(A[i] == 1){
		if(prev == 1) return dp[i][nbr] = 1 + solve(A,N,i+1,0,nbr+1);
		else return dp[i][nbr] = min(solve(A,N,i+1,1,nbr) , 1 + solve(A,N,i+1,0,nbr+1));
	}
	
	else if(A[i] == 2){
		if(prev == 2) return dp[i][nbr] = 1 + solve(A,N,i+1,0,nbr+1);
		else return dp[i][nbr] = min(solve(A,N,i+1,2,nbr) , 1 + solve(A,N,i+1,0,nbr+1));
	}
	
	else if(A[i] == 3){
		if(prev == 1) return dp[i][nbr] = min(solve(A,N,i+1,2,nbr) , 1 + solve(A,N,i+1,0,nbr+1));
		else if(prev == 2) return dp[i][nbr] = min(solve(A,N,i+1,1,nbr) , 1 + solve(A,N,i+1,0,nbr+1));
		else if(prev == 0) return dp[i][nbr] = min(min(solve(A,N,i+1,1,nbr) , solve(A,N,i+1,2,nbr)) , 1 + solve(A,N,i+1,0,nbr+1));
	}
	
}

    int N;
    cin >> N;
    
    int A[N];
    for(int i=0;i<N;++i) cin >> A[i];
    
    memset(dp,-1,sizeof(dp));
    
    cout << solve(A,N,0,0,0);