> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/dong_tai_gui_hua/flip_game.md).

# 博弈类DP, Flip Game

## [Flip Game](https://leetcode.com/problems/flip-game/)

* new String(charArray)
* String.copyValueOf(charArray)

这两种做法在 dfs + backtracking 中都可以正确就地 copy charArray 的值。

```java
    public List<String> generatePossibleNextMoves(String s) {
        List<String> list = new ArrayList<>();
        char[] charArr = s.toCharArray();

        for(int i = 0; i < charArr.length - 1; i++){
            if(charArr[i] == '+' && charArr[i + 1] == '+'){
                charArr[i] = '-';
                charArr[i+1] = '-';

                list.add(new String(charArr));

                charArr[i] = '+';
                charArr[i+1] = '+';
            }
        }

        return list;
    }
```

## [Flip Game II](https://leetcode.com/problems/flip-game-ii/)

博弈类 DP \~ 天然的记忆化搜素，而且状态因为用 String 可以完全表示，也很好处理。

在 recursion 过程中，因为只能把 "++" 变成 "--"，我们每一步的状态空间和选择会越来越小，而且没有回头路或者环。于是每一步之后，新的状态都是一个更小的子问题。

Optimal Substructure: 如果当前状态下，我的任何 move 可以得到一个对手无法获胜的局面，则我当前局面必胜。所以计算过程就是遍历所有可能 move，top-down 记忆化搜索就好了，循环中间可以直接 early termination.

超过 95.83%，速度不错\~

```java
public class Solution {
    public boolean canWin(String s) {
        // Key : current state of game
        // Value : If the current player can win.
        HashMap<String, Boolean> map = new HashMap<>();

        return memoizedSearch(s, map);
    }

    private boolean memoizedSearch(String s, HashMap<String, Boolean> map){
        if(map.containsKey(s)) return map.get(s);

        boolean canWin = false;
        char[] charArr = s.toCharArray();

        for(int i = 0; i < s.length() - 1; i++){
            if(charArr[i] == '+' && charArr[i + 1] == '+'){
                charArr[i] = '-';
                charArr[i + 1] = '-';

                boolean rst = memoizedSearch(new String(charArr), map);
                if(!rst){
                    canWin = true;
                    break;
                }

                charArr[i] = '+';
                charArr[i + 1] = '+';
            }
        }

        map.put(s, canWin);

        return canWin;
    }
}
```