本题一开始想的是与飞行员兄弟相同，枚举每个方案，然后判断是否合法，得到最小步数，但毫无疑问会超时。

暴力解法

package AL;

import java.util.*;

public class A1208_翻硬币test {
static int N=110;
// 记录每组硬币的状态  翻转还是不翻转
    static int[] st=new int[N];

    static int n=0;
    static char[] s;
    static char[] d;
    static char[] temp=new char[N];
    static int res=Integer.MAX_VALUE;
    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);

        s=sc.next().toCharArray();
        n=s.length;
         d=sc.next().toCharArray();

        dfs(0);
        System.out.println(res);






    }


    public static void dfs(int x) {



        if(x>n) {
            //拷贝数组
            for(int i=0;i<s.length;i++) {

                temp[i]=s[i];

            }

            int count=0;
            for(int i=0;i<=n-2;i++) {

                if(st[i]==1) {
//                  System.out.println(i);
                    // 进行翻转
                    turn_one(i);
                    count++;
                }


            }



            // 判断是否符合要求
            boolean flag=true;
//          System.out.println(new String(s));
            for(int i=0;i<s.length;i++) {
                if(s[i]!=d[i]) {
                    flag=false;
                }
            }

            if(flag) {

                res=Math.min(res, count);
            }


            //拷贝数组
            for(int i=0;i<s.length;i++) {

                s[i]=temp[i];

            }


            return;
        }


        st[x]=1;
        dfs(x+1);
        st[x]=0;

        // 不翻转
        st[x]=2;
        dfs(x+1);
        st[x]=0;








    }

    public static void turn_one(int x) {
        if(s[x]=='o') {
            s[x]='*';
        }else {
            s[x]='o';
        }

        if(s[x+1]=='o') {
            s[x+1]='*';
        }else {
            s[x+1]='o';
        }


    }


}

正确解法
1.求最少的步数 因此最优解是每个硬币只翻转一次
2. 顺序不影响最终结果

首先考虑第一个硬币的状态，他的状态只能由第一个硬币自己决定，因此如果第一个硬币的状态和答案中第一个硬币状态不同的话，就需要翻转第一个硬币，让他们相同。

考虑到最优解是每个硬币只翻转一次，因此此时第一个硬币确定后不能再翻转，则第二个硬币的状态只能由第二个硬币自身决定,不能再由第一个硬币翻转影响，若与最终状态相同 则不翻转；否则翻转 以此确定第二枚硬币是否翻转。

之后的硬币同上考虑类推…每个硬币实际都由自身决定翻不翻转 翻转到最后一个硬币时，前n-1个硬币的状态一定已经是最终状态，若此时最后一个硬币状态与最终状态不同，则无解。

package AL;

import java.util.*;

public class A1208_翻硬币 {
static char[] s;
static char[] d;

    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);
         s=sc.next().toCharArray();
         d=sc.next().toCharArray();


        // 由于第一个硬币的状态只能由第一个硬币决定 
        // 第二个硬币的状态本来是由第一个硬币和第二个硬币的状态决定的  但是第一个硬币的状态已经确定 和最终答案保持一致
        // 若多翻转则一定不是最优解  因此第二个硬币的状态只能由第二个硬币决定  以此递推
        // 每个硬币的状态都只能由自己决定  
        // 翻转到最后一个硬币时 前n-1个硬币的状态一定是已经和答案保持一致的 此时若最后一个硬币状态和答案不同 则说明无解



    // 比较状态
         int count=0;
        for(int i=0;i<s.length-1;i++) {
            if(s[i]!=d[i]) {
                // 翻转
                turn_one(i);
                count++;
            }




        }
        System.out.println(count);



    }

    public static void turn_one(int x) {
        if(s[x]=='o') {
            s[x]='*';
        }else {
            s[x]='o';
        }



        if(s[x+1]=='o') {
            s[x+1]='*';
        }else {
            s[x+1]='o';
        }
    }



}