I was learning Paint fence algorithm: n fences, k colors, how many ways to paint the n fences such that atmost 2 adjacent fences have the same color. For more details link.
I tried the standard solution, but I think this is wrong, or I did understand the problem wrong.
Look for the test case n = 4, k = 3, result from the standard algorithm is 66, but if I try the brute force method, then I got 60.
Standard DP approach counts 6 more than brute force.
My brute force code:
string s;
int n;
int ans;
void permute(int idx){
if(idx == n){
int cnt = 0;
for (int i = 0; i < n-1; ++i){
if(s[i] == s[i+1]) cnt++;
}
if(cnt <= 1){
cout << s << endl;
ans++;
}
return;
}
for (char ch: {'A', 'B', 'C'}){
s[idx] = ch;
permute(idx+1);
}
}
int main(){
cin >> n;
s = "ABCD";
permute(0);
cout << ans;
return 0;
}
Could you please explain what is wrong.