294. Flip Game II

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive “++” into “–”. The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

For example, given s = “++++”, return true. The starting player can guarantee a win by flipping the middle “++” to become “+–+”.

Follow up:
Derive your algorithm’s runtime complexity.

解法1：DFS O(N!!)

每次尝试一个可以flip的位置，然后进行下一轮，如果下一轮的人不能获胜，则证明first player可以赢。
Time Complexity 按照这个人说的：

For the time complexity, here is what I thought, let's say the length of the input string s is n, there are at most n - 1 ways to replace "++" to "--" (imagine s is all "+++..."), once we replace one "++", there are at most (n - 2) - 1 ways to do the replacement, it's a little bit like solving the N-Queens problem, the time complexity is (n - 1) x (n - 3) x (n - 5) x ..., so it's O(n!!), double factorial.

C++

Java

解法2： DP

参考这篇：https://leetcode.com/problems/flip-game-ii/discuss/