【Paiza】2項間漸化式 1【レベルアップ問題集】

はじめに

IT／WEBエンジニアに特化した転職・就職・学習サイト「paiza（パイザ）」のレベルアップ問題集から１問ピックアップして、とことん噛み砕いた解説を備忘録としてまとめました。

今回は「DPメニュー」から「2項間漸化式 1」を解説していきます。

問題

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

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

解説

動的計画法では、

• 部分問題 に分ける
• DPテーブル を作成する

ことが重要です。

部分問題に分ける

部分問題 について考える際は、「最後から」手順を追っていくことがポイントとなります。今回の問題では k 項目の値、すなわち a_k を得ることが目的です。ここで、与えられた数列の式から a_k は a_{k-1} + d で表されることが分かります。次に a_{k-1} について考えると、これは a_{k-2} + d で表されます。このようにして考えると、a_k は a_1 ~ a_{k-1} が分かれば求められることが分かります。

DPテーブルを作成する

先ほど、部分問題に分けて考えたことによって a_k は a_1 ~ a_{k-1} が分かれば求められることが判明しました。ということは、a_1 から順番に計算していけばいいということになります。ここで、計算結果を収める DPテーブル を作成します。今回は a_1 ~ a_k までの計算結果を格納したいため、DPテーブルは以下のようになります。ここで、DPテーブルの最初の値 dp[0] は当然 a_1 すなわち x となります。

DPテーブルの作成

dp = [None] * k
dp[0] = x

また、最初の値以降は前項の値に d を足したものであるため、DPテーブルは以下のように更新すれば良いことが分かります。

DPテーブルの更新

for i in range(1, k):
    dp[i] = dp[i-1] + d

こうしてDPテーブルが作成できました。

解答例

以上の解説を踏まえた解答コードです。
問題文では Index が 1 からスタートしていますが、Python では 0 からスタートすることに注意してください。

解答例(Python)

# 入力値の取得
x, d, k = map(int, input().split())

# DPテーブルの初期化
dp = [None] * k
dp[0] = x

# DPテーブルの更新
for i in range(1, k):
    dp[i] = dp[i-1] + d

# 結果の表示
print(dp[k-1])