\(dp[S] = \)(まだ残っている物の番号の集合が \(S\) であるとき，すべての物を倒すのに必要なボールの回数の期待値) という DP を考えます．

この DP は，ボールの狙いを定める座標を \(0\) 以上 \(15\) 以下の整数値で全探索することにより（これ以外の座標に狙いを定めることは明らかに無駄です），次のように遷移できます：

• \(dp[S] = \max _{0 \leq j \leq 15} (\sum_{k \in \{j-1, j, j+1\} \cap k \in S} \dfrac{1}{3} dp[S \backslash k] + \sum_{k \in \{j-1, j, j+1\} \cap k \notin S} \dfrac{1}{3} dp[S] + 1)\)

この遷移に従って，小さい集合から順に求めればよいです．この式には \(dp[S]\) の項に関して自己ループが含まれるため，実際に計算する際には \(dp[S]\) の項を左辺に集めることで自己ループを除去する必要があることに注意してください．計算量は \(L = 16\) として \(O(L2^N)\) となります．