問題
C: 柱柱柱柱柱 - AtCoder Beginner Contest 040 | AtCoder
解き方
全探索では計算量がO(2n)となり間に合わない。よって動的計画法を用いて解く。
なぜ動的計画法が使えるか
部分問題を解き、その計算結果を保存し再利用することで全体の問題が解ける。i番目の柱に到達する方法は、i - 1番目からとi -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]に代入する際に、既に保存してあったものと比べて小さいものを採用する。
動的計画法の関数を立てる
上記から以下のように関数を書くことができる
