题目
你有一块沿网格压好痕的巧克力，大小为\(6\times4\)个小方块。你想把它掰成所有单独的小方块。
每一步你可以拿起其中一块，沿该块上的某一条横向或纵向压痕掰开。
例如，可以先掰\(3\)次把它变成\(4\)条、每条\(6\)块；再把每一条各掰\(5\)次，就总共用了\(3+4\times5=23\)次。
你能做得更好吗？
分析
不能。最少就是\(23\)次。
关键不变量是“块数”。
- 开始时整块巧克力只有\(1\)块。
- 每次合法掰开，都是把“某一块”分成“两块”，所以总块数恰好增加\(1\)。
目标是得到\(6\times4=24\)个小方块，因此块数必须从\(1\)增加到\(24\)，总共增加\(23\)。
而每次操作最多只增加\(1\)块，所以无论策略如何，至少要\(23\)次。
题目给出的做法正好用了\(23\)次，已经达到下界，所以最优值就是\(23\)次，不能更少。
更一般地，\(m\times n\)的巧克力最少需要\(mn-1\)次。