もしパワーアップアイテムがなければこの問題はTSP(巡回セールスマン問題)なので、 \(\mathrm{DP}[S][v]\) を「拾ったコインの集合が \(S\) で、今いる座標が \(v\) (いずれかのコインの座標)である状態に至るまでの最小移動回数」と定めるDPにより解くことができます。

パワーアップアイテムがある元の問題でもほとんど同様に、\(\mathrm{DP}[S][f][v]\) を「拾ったコインの集合が \(S\) で、パワーアップしたかどうかが \(f\) で、今いる座標が \(v\) (いずれかのコインの座標またはパワーアップアイテムの座標)である状態に至るまでの最小移動回数」と定めるbitDPにより解くことができます。