部内勉強会（３） - octoの勉強記録

第3回　動的計画法入門編（１）

動的計画法：全探索する際にそれぞれの計算で値を記録しておくことによって繰り返し計算をなくすことによって高速化する手法．

いろいろ典型テクニックがあるけど今回は初歩的なDPとDPの計算量の見積もりについて勉強します．

漸化式を立てる

漸化式を立てることがDPの基本です．DPは一度計算した結果を記録するので初項から順に計算すれば，それぞれの項を１回の計算で求めることができます．
状態遷移を考える

漸化式を立てれたら状態遷移を式にしてみましょう

今回の問題の場合は

dp[i] = i段目まで登る場合の数

a[i] ：壊れていると0，使えるなら1

とすると

dp[i] = dp[i-1]*a[i-1]+dp[i-2]*a[i-2]

となります
初期状態を決めて実装する

後は初期状態が決まればすべての段について到達できる場合の数を求められます

今回はdp[0] = 1として配るDPをしてみましょう

配るDPとは？

けんちょんさんの記事が分かりやすいです

貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題

配るDPは既に結果が分かっている部分から遷移先を計算していく方式です．結果を配っていくイメージ

貰うDPとはまだ結果が分からない部分を全ての遷移元の情報から計算する方式です．結果をもらってくるイメージ

今回はもらうDPを使用とするとdp[1]を計算するときに範囲外参照をしてしまうので配るDPで書いてみましょう．