\(\mathrm{dp}_i\)を \(i\) 番目以降のラウンドで獲得できる金貨の枚数の期待値の最大値とします。これを \(i\) の降順に求めることにすると、高橋君が袋に金貨を入れる場合と入れない場合で獲得できる金貨の枚数の期待値がどうなるかを求められるため、より良い高橋君の戦略(期待値が大きい方)も分かります。よって、時間計算量 \(\mathrm{O}(N)\) で本問を解くことが出来ます。

本問のように期待値の最大化を考える問題を動的計画法で解く時、例えば \(\mathrm{dp}_i\) を \(i\) 番目のラウンドが終了した時点で獲得できる金塊の枚数の期待値の最大値等と定めて \(i\) の昇順に求めることにすると困難が生じます。なぜなら、高橋君が \(i\) 番目のラウンドで金貨を袋に入れるか否かは \(i+1\) 番目以降のラウンドの様子に依存するためです。一方、上述のように最後のラウンドから期待値を求めると \(i+1\) 番目以降のラウンドの様子が分かり、うまくいくことが多いです。