题目

题意：
给定两个字符串不妨取第一个字符串为s，第二个字符串为t，这些字符串是由硬币组成的，o(小写字母)代表反面，'*'代表正面，可以同时翻转两个相邻的硬币，问最少需要翻动多少次

思路：
一种暴力思路是直接dfs搜索，注意剪枝优化即可，另外一种是递推即使定义这样一种状态：
f(x): 前x个字符前都是相同的，那么如果第x个字符不相同就翻转第x个和第x+1个即可，同时更新翻转次数，直到倒数第一个便可求出答案，题目保证有解。

代码：

第一种递推
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<map>
#include<queue>
#include<vector>
#include<cmath>

using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;

    int cnt = 0;
    int len = s.size();
    for (int i = 0; i < len; i++) {
        if (s[i] != t[i]) {
            cnt++;
            if (s[i + 1] == '*') s[i + 1] = 'o';
            else s[i + 1] = '*';
        }
    }
    cout << cnt << '\n';
    return 0;
}


第二种：递归

#include<bits/stdc++.h>

using namespace std;

string t;
int ans;
int len;

void swap(char &p,char &q)
{
    if(p=='*') p='o';
    else p='*';
    if(q=='*') q='o';
    else  q='*';
}

void dfs(int x,string s,int cnt)
{
    //cout<<s<<'\n';
    if(s==t) {
        //cout<<"hhh\n";
        //cout<<s<<'\n';
        ans=min(ans,cnt);
        return ;
    }
    if(cnt>ans||x>=len) return ;



    //翻转第x个位置以及第x-1 
    if(s[x-1]!=t[x-1]) {
        swap(s[x],s[x-1]);
        dfs(x+1,s,cnt+1);
    } 
    else {
        //不翻转
        dfs(x+1,s,cnt); 
    }
    //swap(s[x],s[x-1]);
}

int main()
{
    string s;
    cin>>s>>t;
    len=s.length();
    ans=0x3f3f3f3f;
    dfs(1,s,0);
    cout<<ans<<'\n';
    return 0;   
}