Flip Game II

https://www.lintcode.com/problem/flip-game-ii/description

public class Solution {
    /**
     * @param s: the given string
     * @return: if the starting player can guarantee a win
     */
    public boolean canWin(String s) {
        // write your code here
        boolean[] dp = new boolean[s.length()];
        for (int i = 0; i < dp.length; i++) {
            if (s.charAt(i) == '+') {
                dp[i] = true;
            }
        }
        return treeWalk(dp);
    }

    private boolean treeWalk(boolean[] dp) {
        for (int i = 1; i < dp.length; i++) {
            if (dp[i - 1] && dp[i]) {
                dp[i - 1] = false;
                dp[i] = false;
                if (!treeWalk(dp)) {//对方没有赢
                    dp[i - 1] = true;
                    dp[i] = true;
                    return true;
                }
                dp[i - 1] = true;
                dp[i] = true;
            }
        }
        return false;
    }
}