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](https://www.geeksforgeeks.org/painting-fence-algorithm/).↵
↵
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;↵
}↵
~~~~~↵
↵
I think standard code also counts these 6 permutations:↵
↵
`[AABB], [BBAA], [CCAA], [AACC], [BBCC], [CCBB]`↵
↵
Could you please explain what is wrong.↵
↵
↵
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;↵
}↵
~~~~~↵
↵
I think standard code also counts these 6 permutations:↵
↵
`[AABB], [BBAA], [CCAA], [AACC], [BBCC], [CCBB]`↵
↵
Could you please explain what is wrong.↵
↵
