今回から paiza の DPメニュー（動的計画法）の問題に挑戦していく！
問題概要
-
与えられる入力：
初項 x、公差 d、求めたい項数 k -
数列の定義：
a₁ = x
aₙ = aₙ₋₁ + d（n ≧ 2） -
目的：
この等差数列の 第 k 項 aₖ を求めて出力する
🔍 この問題の意図と目的
DP（動的計画法）の基本構造に慣れることが目的。
「すでに解いた部分（a[1]～a[k-1]）」を利用して「次の値（a[k]）」を求めるという考え方を体験する。
実際には公式 aₖ = x + (k – 1) * d で1行で求められるけど、それをあえて ループと配列で構築するのが練習のポイント。
DP は、一言でいうと「問題を部分問題に分割し、部分問題の答えを記録しながら、それらを利用することによって元の問題の答えを得る手法」です。
🧩 解き方のステップ（DP）
-
初期値の設定：
a[1] = x -
漸化式の利用：
a[i] = a[i – 1] + dを i = 2 から k まで繰り返す -
最終出力：
a[k]を表示する
入力される値
x d k
期待する出力
a_k
入力例:
0 7 9
出力例:
56
✅OK例：
// a[1] <- x
// for i = 2 to k
// a[i] <- a[i-1] + d
// print a[k]
const rl = require('readline').createInterface({ input:process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [x, d, k] = lines[0].split(' ').map(Number);
const a = [0, x];
for(let i = 2; i <= k; i++){
a[i] = a[i-1] + d;
}
console.log(a[k]);
});
例：配列なし・変数
let a = x;
for (let i = 2; i <= k; i++) {
a += d;
}
console.log(a);
補足：1行で書くなら？
実際には等差数列なので、次のように1行で解ける：
console.log(x + (k - 1) * d);
でも今回の練習はDPの構造に慣れることが目的なので、あえてループを使って「1つ前の値から次の値を作る」やり方で書いている。
📌 まとめ：
- DPの基本形の練習をした（漸化式 + 初期値 + ループ）
- 配列に値を蓄積しておくことで、次のステップに使える
🔁 漸化式（ぜんかしき）とは？
漸化式とは、「ある項を前の項（または前のいくつかの項）を使って表す式」。
📘 例：等差数列
たとえば、次のような数列を考えてみよう。
a₁ = 3
a₂ = a₁ + 2 = 5
a₃ = a₂ + 2 = 7
a₄ = a₃ + 2 = 9
...
この数列は、「前の項に2を足す」ことで次の項が決まっている。
つまり、次のように書ける：
a₁ = 3
aₙ = aₙ₋₁ + 2（n ≧ 2）
この「 aₙ = aₙ₋₁ + 2 」が 漸化式 。
🧠 漸化式はこんなときに使う
- 動的計画法（DP）で「1つ前の答えを使って次を求める」
- 数列や再帰の定義（フィボナッチ数列など）
- 関数の再帰的な関係を表すとき
🧮 フィボナッチ数列の漸化式
もっと有名な例として、フィボナッチ数列も漸化式で定義されている：
f₀ = 0
f₁ = 1
fₙ = fₙ₋₁ + fₙ₋₂（n ≧ 2）
✅ ポイント
- 「漸（ぜん）」＝少しずつ進む（前の値に依存）
- 「漸化式」＝次の値を、前の値で作るためのルール
- DP（動的計画法）では、漸化式がスタート地点！