首先打表出只有三根柱子时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]);
}
}