2項間漸化式 1 Erlang(Beta)編（paizaランク C 相当）

(はじめに)

このメニューでは、動的計画法 (Dynamic Programming, 以下 DP と表記します) について扱います。

DP は、一言でいうと「問題を部分問題に分割し、部分問題の答えを記録しながら、それらを利用することによって元の問題の答えを得る手法」です。

問題をどのように分割するか、部分問題の答えをどのように利用するかなどは問題により異なります。このメニューを通してさまざまなDPの問題に触れ、そのノウハウを身につけていきましょう。

まずは、早速問題を見てみましょう。

---

(問題)

整数 x, d, k が与えられます。
次のように定められた数列の k 項目の値を出力してください。

・ a_1 = x
・ a_n = a_{n-1} + d (n ≧ 2)

---

(ヒント)

等差数列の公式を使えばDPを使わずとも答えを求めることができますが、練習だと思ってDPで解いてみましょう。

DPを考える際には、まず漸化式を考えるとよいです。漸化式は、数列の各項をその前の項を用いて記述した式です。問題で与えられている a_n = a_{n-1} + d という式がこの問題における漸化式となっています。

では、実際にこの問題を解いてみましょう。最終的に求めたいのは a_k です。a_1 ~ a_{k-1} がわかっているとして、a_k がどうなるかを考えてみましょう (a_1 ~ a_{k-1} が、「はじめに」の部分で述べた"部分問題"に相当しています) 。a_{k-1} がわかっているので、a_k = a_{k-1} + d とすればよいですね。今回は a_1 が x であることがわかっているので、順に a_2, a_3, a_4, ... を計算していけば a_k が求まることがわかるかと思います。

以下の疑似コードを参考にして、あなたの得意な言語で実装してみましょう。

a[1] <- x

for i = 2 to k
    a[i] <- a[i-1] + d

print a[k]