单词博弈

单词博弈

Wait to Finish

题目

甲乙两个人用一个英语单词玩游戏。两个人轮流进行，每个人每次从中删掉任意一个字母，如果剩余的字母序列是严格单调递增的（按字典序a < b < c <….

输入说明

1. 输入： 一连串英文小写字母，长度不超过15,保证最开始的状态不是一个严格单增的序列。 
2. 输出：1表示甲可以赢，0表示甲不能赢。

测试用例

1. 输入 bad， 则甲可以删掉b或者a,剩余的是ad或者bd，他就赢了，输出1。 
2. 输入 aaa， 则甲只能删掉1个a，乙删掉一个a,剩余1个a，乙获胜，输出0。

其实一看到长度不超过15，2<<15+dp+dfs，做法就已经很明显思路已经很明晰了。但此外一见到这种都会不自主想到Nim游戏博弈和SG函数，看能不能找到规则十分简单但又无比优美的结论。Nim和SG会出现在很多算法书的最开始的部分，一些作者都会热衷于讲解它们。原因我认为是，Nim和SG是机器算法、数学和博弈学的巧妙结合的经典例子，其过程带着微妙巧合的同时又处处充斥着严谨的逻辑思想，和dp、树、图等最能展示算法的独特魅力。

Java代码实现

package huawei;

import java.util.Arrays;
import java.util.HashMap;

public final class Demo
{
	public int who(String input)
	{
		int len=input.length();
		int[] dp=new int[1<<len];
		int[] isAsc=new int[1<<len];
		Arrays.fill(dp, -1);
		Arrays.fill(isAsc, -1);
		return dfs((1<<len)-1,input,dp,isAsc,len);
	}
	
	public static int dfs(int num,String input,int[] dp,int[] isAsc,int len){
		if(dp[num]!=-1) return dp[num];
		if(countOne(num)==2){
			dp[num]=1;
			return 1;
		}
		int tem;
		dp[num]=0;
		for(int erase=1;erase<num;){
			tem=num-erase&num;
			if(tem!=num){
				if(dfs(tem,input,dp,isAsc,len)==0||judgeAsc(tem,input,isAsc,len)==1){
					dp[num]=1;
					return 1;
				}
			}
			erase<<=1;
		}
		return dp[num];
	}
	
	public static int countOne(int n){
		int res=0;
		while(n!=0){
			n=n&(n-1);
			res++;
		}
		return res;
	}
	
	public static int judgeAsc(int n,String str,int[] isAsc,int len){
		if(isAsc[n]!=-1) return isAsc[n];
		if(countOne(n)==1){
			isAsc[n]=1;
			return 1;
		}
		int next=123;
		for(int i=0;(1<<i)<=n;i++){
			if((n&(1<<i))!=0){
				if(str.charAt(len-1-i)>=next){
					isAsc[n]=0;
					return 0;
				}
				next=str.charAt(len-1-i);
			}
		}
		isAsc[n]=1;
		return 1;
	}
	
}