因为如果首个位置要留给后面的 I 人，那么这个 A 人就得放弃（前面没有非空的有空桌子）
那为什么不选择让这个 A 人坐下，放弃后面那个 I 人，这样这个 A 人和 I 人之前的 E 人就有机会找到座位
这两个方案代价一致，但是带来收益完全可以被覆盖，故上面这条成立
这是一个汉诺塔题，但是，正常情况下，每一个块必须是上面没有其他块的时候才可以移动，而这里变成了：
上面必须恰好要有 $a_i$ 块的时候，$i$ 才能移动，且仅移动 $i$ 本身（不移动其上面的部分）
我们定义当前汉诺塔有三个柱子：base(当前所在的), tmp(用来华容道的), target(目标移动到的)
对于有 $n$ 个块的汉诺塔，我们可以得到两个显而易见的结论：
- 对于方块 $n$，无论它在哪，并不影响其他的方块移动：因为它是最大的那个方块，任何方块都可以放到它上面，它相当于基座
- 汉诺塔的三座塔等价，即在任何时候，如果 $\exists$ 一种操作，可以将 $x$ 高度的汉诺塔从 base 移动到 target，那么必然存在几乎相同的操作将其移动到 tmp
所以我们可以得到如下的汉诺塔递推公式：
通常情况下，我们会使用递推公式直接计算通项公式或者直接算出目标值，事实上，我们仍然可以使用递归来真实计算
这里由于需要考虑到拆分（需要保留一些块在当前块上，当前块才可以移动）
所以我们定义一个新的 $g(i, j)$ 表示：初始且保持 $1 \to (j - 1)$ 在 tmp 的情况下，让 $j \to i$ 这 $i - j + 1$ 块从 base 移动到 target 需要的步数
此时 A 块表示的就是 $1 \to (j - 1)$ 块部分，而 B + C + X 表示 $j \to i$ 部分
其中 X 表示就是第 $i$ 行， C 表示 $a_i$ 部分，而 B 就是多出来的部分
$$ \begin{matrix} A \to target \\ B \to tmp \\ A \to tmp \\ X \to target \\ C \to target \\ A \to base \\ B \to target\\ A \to tmp \end{matrix} $$
其中 X 表示就是第 $i$ 行，此时 C + X 块表示的就是 $j \to i$ 块部分
而 A + C 恰好为 $a_i$，A + B 为 $1 \to (j - 1)$，B 为剩余部分
$$ \begin{matrix} A \to base \\ X \to target \\ A \to tmp \\ C \to target \end{matrix} $$
1 | |
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。