3本の柱A、B、Cがあります。A柱には大きさの異なるN個の円盤が通してあり、大きい円盤が下、小さい円盤が上にあります。A柱の円盤をすべてC柱に移動させる必要があります。大きい円盤が下、小さい円盤が上という規則を保ちます（B柱を利用してもよい）。各移動では、1本の柱の一番上の円盤を別の柱の一番上に移動させることしかできません。移動過程を出力してください。

解答

これは動的計画法問題の一種であり、再帰を使って実装するのが比較的簡単で便利です。

「moveSum個の円盤をfrom柱からto柱へ移動する（by柱を利用する）」という問題は、以下の3つのステップで実現できます。

• from柱の一番上のmoveSum-1個の円盤をby柱へ移動します（to柱を利用）
• from柱に残った1個の円盤を直接to柱へ移動します
• by柱のmoveSum-1個の円盤をto柱へ移動します（from柱を利用）

実行の流れは次のとおりです：

原文リンク：https://blog.51cto.com/myunix/2399892