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