AcWing
1208. 翻硬币
递推。对于某一连续的硬币对，其要么翻动，要么保持不变。从硬币的首个位置开始遍历：对于第1个位置，只能更新/保持第1个硬币对，使得第1个硬币的状态为目标状态；对于第2个位置，只能更新/保持第2个硬币对(不能更新第1个硬币对，因为第1个位置的状态已经确定)，使得第2个位置的状态为目标状态，…，对于第n - 1个位置，只能更新/保持第n - 1个硬币对(也是最后一个硬币对)，使得第n - 1个位置的状态为目标状态。此后，最后一个硬币的状态一定是目标状态(因为题目一定有解)。
#include <bits/stdc++.h>
using namespace std;
string s1, s2;
void turnone(int idx){
if(s1[idx] == 'o') s1[idx] = '*';
else s1[idx] = 'o';
}
int main(){
cin >> s1 >> s2;
int res = 0;
for(int i = 0; i <= s1.size() - 2; i++){
if(s1[i] != s2[i]){
turnone(i);
turnone(i + 1);
res++;
}
}
cout << res << endl;
return 0;
}