太离谱了！领导的现任居然是我的前女友。。。

这两天刷题的时候，看到了一道挺有意思的算法题——祖玛游戏。说实话，第一眼看到题目，我还以为是什么经典的消除游戏要做个模拟，心里咯噔了一下，毕竟模拟题有时候比动态规划还磨人。

但咱干这一行的，遇事不能慌，先分析再动手。题目大概意思是：桌面上有一排彩球，你手里也有一些球。每次你可以把手里的球插入桌面上任意位置，只要有三个或以上颜色相同的球连在一起，就可以消除掉。这波消除可能会触发连锁反应，直到不能再消除为止。你的任务就是用最少的球，把桌面上的球全部清空。如果清不了，就返回 -1。

祖玛的艺术，咱不懂，但祖玛的代码，咱还是能写一写的。思路上，这玩意一看就像搜索问题，标准的“试一试所有可能”那一挂。DFS走起，外加点剪枝，不然栈都爆了。

这时候可能会有小伙伴问：兄弟，这玩意能不能用贪心或者DP？我摇了摇头，这题目贪不下去，DP也难搞。因为插球的位置、触发的消除、连锁反应，全是动态变化的，状态空间太大，没法稳稳地列个表。

言归正传，咱上代码：

classSolution {
publicint findMinStep(String board, String hand) {
int[] count = new int[26];
for (char c : hand.toCharArray()) count[c - 'A']++;
int res= dfs(board, count);
return res == Integer.MAX_VALUE ? -1 : res;
    }

privateint dfs(String board, int[] count) {
if (board.isEmpty()) return0;
int i=0, res = Integer.MAX_VALUE;
while (i < board.length()) {
int j= i;
while (j < board.length() && board.charAt(j) == board.charAt(i)) j++;
int need=3 - (j - i); // 需要补几个球才能消除
if (count[board.charAt(i) - 'A'] >= need) {
                count[board.charAt(i) - 'A'] -= need;
String next= board.substring(0, i) + board.substring(j);
                res = Math.min(res, (need <= 0 ? 0 : need) + dfs(removeConsecutive(next), count));
                count[board.charAt(i) - 'A'] += need;
            }
            i = j;
        }
return res;
    }

private String removeConsecutive(String board) {
int i=0;
for (int j=0; j <= board.length(); j++) {
if (j == board.length() || board.charAt(j) != board.charAt(i)) {
if (j - i >= 3) {
return removeConsecutive(board.substring(0, i) + board.substring(j));
                }
                i = j;
            }
        }
return board;
    }
}

简单讲下这个思路，DFS每次找连续相同颜色的球段，看看要不要插球让它消除掉。如果需要，就从手里的球扣出来，递归往下走，等走到底再回溯回来。这里 removeConsecutive 是个递归消除的过程，毕竟人家题目设定的连锁反应，得好好处理。

写到这儿，我就想到以前有个同事写递归，递归得自己都看不懂，变量名一个比一个抽象，看了半天连是干嘛的都不清楚。我是真心建议，写递归尤其是搜索题的时候，变量名写明白点，代码多加点注释，能救命。

再来点段子调剂一下，祖玛这玩意，跟我们程序员熬夜加班似的，球不清完根本停不下来。但凡桌面上还有一个球，你心里就不得劲。项目上线前，Bug要是不清零，哪怕只剩一个，也睡不踏实。

说到底，这题虽然是个搜索题，但最关键的是剪枝。如果没剪枝，光是暴力递归，能让你跑上天。上面这段代码剪得还行，最坏情况也能Hold住，递归深度不过分。DFS配剪枝，算法人生不迷路。

刷完这题，我突然想，程序员和祖玛游戏挺像的，Bug和需求一个接一个，消完一波，后面又冒出来一波，清不完，根本停不下来。你以为写个简单的CRUD就能结束，结果需求改了，接口加了，性能瓶颈冒出来了，真是连锁反应。这就是生活吧，哎。