奇怪的汉诺塔

首先打表出只有三根柱子时 1~12 个圆盘所需的次数，思路是这样的，对于三根柱子，首先将前 i-1 个圆盘移动到某一根柱子，然后将最后一个圆盘移动到一根柱子，最后再将剩下的 i-1 个圆盘移动到一根柱子，所以 three[i] = three[i - 1] + 1 + three[i - 1]

对于四根柱子来说，枚举前 j 个圆盘，首先将前 j 个圆盘移动到四根柱子种的某一根，次数是 four[j]，然后将剩下的 i-j 个圆盘移动到剩下的三根柱子，次数是 three[i-j]（为什么是三根柱子，因为之前已经有一根柱子被占用了，所以这里即使有四根柱子，也只有三根能用），最后再将那 j 个圆盘移回来，次数是 four[j]，所以状态转移方程为 four[i] = min{four[i], four[j] + three[i - j] + four[j]}

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int[] three = new int[13];
        for (int i = 1; i <= 12; i++)
            three[i] = three[i - 1] + 1 + three[i - 1];
        int[] four = new int[13];
        Arrays.fill(four, Integer.MAX_VALUE >> 1);
        four[0] = 0;
        for (int i = 1; i <= 12; i++)
            for (int j = 0; j < i; j++)
                four[i] = Math.min(four[i], four[j] + three[i - j] + four[j]);
        for (int i = 1; i <= 12; i++)
            System.out.println(four[i]);
    }
}