読者です 読者をやめる 読者になる 読者になる

動的計画法を使うことでアスレチックで遊ぶ時に体力の消耗を抑える

AtCoder グラフ理論 メモ化 全探索 動的計画法

問題

C: 柱柱柱柱柱 - AtCoder Beginner Contest 040 | AtCoder

解き方

全探索では計算量がO(2n)となり間に合わない。よって動的計画法を用いて解く。

なぜ動的計画法が使えるか

部分問題を解き、その計算結果を保存し再利用することで全体の問題が解ける。i番目の柱に到達する方法は、i - 1番目からとi -2番目から到達する2つの方法がある。またi番目のコストはi - 2, i - 1番目時点でのコストに、i番目に来るのに必要なコストを足せばOK。

メモ化テーブルを考えう

今回はi番目に到達するときの最小のコストを求めたいのでテーブルは以下のようになる

dp[i] = 最小コスト

漸化式を立てる

上記から漸化式は以下のようになる

dp[i + 1] = dp[i] + iからi + 1に移動するコスト
dp[i + 2] = dp[i] + iからi + 2に移動するコスト

また今回は最小のコストを求めたいので、dp[i + 1], dp[i + 2]に代入する際に、既に保存してあったものと比べて小さいものを採用する。

動的計画法の関数を立てる

上記から以下のように関数を書くことができる

ソースコード