Problem Link: USACO
Here is my code:
ll n;
cin>>n;
vector<ll> v(n);
for(ll i=0;i<n;i++) cin>>v[i];
ll dp[n][n];
for(ll i=0;i<n;i++) dp[i][i]=1;
for(ll i=n-1;i>=0;i--) {
for(ll j=i+1;j<n;j++) {
dp[i][j]=n+1;
for(ll k=i;k<j;k++) {
if(v[k]==v[k+1]) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]-1);
else dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
}
}
}
cout<<dp[0][n-1]<<endl;```
here is a link to the solution given in usaco guide:
https://usaco.guide/problems/usaco-1114-modern-art-3/solution
here's what i am asking:
My code is giving wrong answer on some test cases.The only difference in my code
and the code given in usaco guide is this line -
if(v[i]==v[j]) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]-1);
the if condition is the only difference.I've used if(v[k]==v[k+1]) but the guide
solution has used if(v[i]==v[j]).i think the if condition should be v[k]==v[k+1]
because that's the intersection point of the 2 segments
that we're trying to merge and if those 2 points have the
same colour then we need one less colour than the total so the transition makes
sense to me but i couldn't understand why is the condition v[i]==v[j].