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);