Java dfs + memo solution with prune
\nclass Solution {\n    private int len;\n    private Map<String, Boolean> cache;\n    public boolean stoneGameIX(int[] stones) {\n        cache = new HashMap<>
```\nclass Solution {\n    private int len;\n    private Map<String, Boolean> cache;\n    public boolean stoneGameIX(int[] stones) {\n        cache = new HashMap<>();\n        len = stones.length;\n        int zeros = 0, ones = 0, twos = 0;\n        for(int stone : stones){\n            zeros += (stone % 3 == 0 ? 1 : 0);\n            ones += (stone % 3 == 1 ? 1 : 0);\n            twos += (stone % 3 == 2 ? 1 : 0);\n        }\n        //zeros % 2, duplicate zeros doesn\'t change the result\n        return helper(3, zeros % 2, ones, twos);\n    }\n    private boolean helper(int num, int zeros, int ones, int twos){\n        if(num == 0){\n            return true;\n        }\n        String key = zeros + "," + ones +"," + twos + "," + num;\n        if(cache.containsKey(key)){\n            return cache.get(key);\n        }\n        if(zeros == 0 && ones == 0 && twos == 0){\n            return len % 2 != 0; \n        }\n        boolean canWin = false;\n        //try pick zero, one or two\n        if(!canWin && zeros > 0 && num % 3 != 0){ \n            if(!helper((num + 0) % 3, zeros - 1, ones, twos)){\n                canWin = true;\n            }\n        }\n        if(!canWin && ones > 0 && num % 3 != 2){\n            if(!helper((num + 1) % 3, zeros, ones - 1, twos)){\n                canWin = true;\n            }\n        }\n        if(!canWin && twos > 0 && num % 3 != 1){\n            if(!helper((num + 2) % 3, zeros, ones, twos - 1)){\n                canWin = true;\n            }\n        }\n        cache.put(key, canWin);\n        return canWin;\n    }\n}\n```
['Java']