Question

有一个java题需要解答

甲乙两个人用一个英语单词玩游戏。两个人轮流进行，每个人每次从中删掉任意一个字母，如果剩余的字母序列是严格单调递增的（按字典序a < b < c <....<z)，则这个人胜利。两个人都足够聪明，甲先开始，问他能赢么？
输入： 一连串英文小写字母，长度不超过15,保证最开始的状态不是一个严格单增的序列。
输出：1表示甲可以赢，0表示甲不能赢。
例如: 输入 bad， 则甲可以删掉b或者a,剩余的是ad或者bd，他就赢了，输出1。
又如: 输入 aaa， 则甲只能删掉1个a，乙删掉一个a,剩余1个a，乙获胜，输出0。
函数头部：
Java：public static int who(String in);

Answer 1

感觉就是一个递归，甲先操作，然后甲模拟乙进行操作，最后通过层层递归甲就能模拟出最终能否获胜了，就是效率可能有点低，时间复杂度可能是O(n)²

追问

能否上代码，谢谢

追答

。。。。代码你自己写吧，只要明白了思路，代码不难的啊。
关键是实现流程，你要思考我说的是不是最优的方案，是否还有更好的方案。我觉得这个问题的主要解决思路肯定是递归，就看递归过程中能否有优化的点提升递归效率了。