博弈类DP, Flip Game

Flip Game

• new String(charArray)

• String.copyValueOf(charArray)

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

    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

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

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

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

超过 95.83%，速度不错~

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;
    }
}