問題

解き方

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

部分問題を解き、その計算結果を保存し再利用することで全体の問題が解ける。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]に代入する際に、既に保存してあったものと比べて小さいものを採用する。

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