在《算法竞赛进阶指南》上也有证明，设 $d_n$ 代表求解 $n$ 盘 $3$ 柱的最少步数，那么我们可以将这个 $4$ 柱分解成两个 $3$ 柱的来看，设 $f_n$ 代表求解 $n$ 盘 $4$ 柱的最少步数，则有递推式：

其中 $f_1=1$，代表我们先把 $i$ 个盘子移动到 $B$ 柱，将 $n-i$ 个盘子移动到 $D$ 柱，最后把 $i$ 个盘子移动到 $D$ 柱。

时间复杂度严格小于 $O(1+3 \times \sqrt{n})$。

代码就不放了。

番外：

做这个题的时候是大佬 @Programming_Konjac 打表发现了一些规律后先 AC 了，后来他告诉我，我也 AC 了，再后来大佬 @zouyihang 对这个式子进行了证明并成功，同时，他也对这个题目进行了复杂度的进一步优化，有望搞到 $O(1)$。目前好像到了 $O(\log n)$，具体的我现在也不清楚。至后期我发现了在《算法竞赛进阶指南》上也有这道题目做法的证明。