2019-02-02 Educational DP Contest / DP まとめコンテスト I - Coins 動的計画法(DP) 問題 提出コード 解法 確率です。 番目までのコインを投げて、表が回出る確率、とします。 もちろん、です。 答えは、 (ただし、 )の総和になります。 番目までのコインを投げて回表が出ていた場合、番目のコインを投げると表の回数がになるか、になります。前者はの確率を引いて裏が出た場合、後者はの確率を引いて表が出た場合です。 これをもとにして遷移を考えると、 となります。あとは遷移をもとにDPを行い、合計値を求めれば答えになります。