今回は paiza の DPで「最安値を達成するには 1」の問題に挑戦！
階段の上り方を調べるのが終わって、次はりんごを最安値で買うパターンをDPの考え方で調べていく！
問題概要
- りんご1個が
a円、りんご2個がb円。 - ぴったり
n個以上のりんごを買うときの最小金額を求める。 - n+1 個以上になってもOK。
〇入力
n a b
- 1 ≤ n ≤ 1,000
- 1 ≤ a < b ≤ 10,000
〇出力
最小金額
入力例：
5 100 150
出力例：
400
✅OK例：
const rl = require('readline').createInterface({ input:process.stdin });
const lines = [];
rl.on('line', (input) => lines.push(input));
rl.on('close', () => {
const [n, a, b] = lines[0].split(' ').map(Number);
const dp = [];
dp[0] = 0;
dp[1] = a;
for (let i = 2; i <= n; i++) {
dp[i] = Math.min(dp[i-1] + a, dp[i-2] + b);
}
console.log(dp[n]);
});
🔍考え方
- 部分問題を定義する：
- dp[i] = りんご i 個を買うのに必要な最小金額
- 最後に買うのは必ず「1個」または「2個」
- 1個買うなら → dp[i-1] + a
- 2個買うなら → dp[i-2] + b
- この２通りのうち安いほう
- よって漸化式：
dp[i] = Math.min(dp[i-1] + a, dp[i-2] + b)
初期条件
-
dp[0] = 0（何も買わないとき金額0） -
dp[1] = a（1個は1個買うしかない、 a < b）
計算の流れ（例: n=5, a=100, b=150）
| i | dp[i] | 計算根拠 |
|---|---|---|
| 0 | 0 | 初期値 |
| 1 | 100 | a円で1個 |
| 2 | 150 | min(100+100, 0+150) = 150 |
| 3 | 250 | min(150+100, 100+150) = 250 |
| 4 | 300 | min(250+100, 150+150) = 300 |
| 5 | 400 | min(300+100, 250+150) = 400 |
答え = dp[5] = 400
一応ツリー構造で視覚化
dp[5] ← min(
dp[4] + a,
dp[3] + b
)
/ \
dp[4]+100 dp[3]+150
/ \ / \
dp[3]+100 dp[2]+150 dp[2]+100 dp[1]+150
/ \ / \ / \ \
... ... ... ... ... ... ...
-
各ノードは「残りi個を買うのに必要な最小金額」を表す
-
枝は「最後に1個買う」または「最後に2個買う」の2通り
-
根（dp[n]）から葉（dp[0], dp[1]）まで展開される
-
実際のDP計算では、このツリー全体を明示的に展開せず、下から順に配列や変数で埋めていく
📝学習のまとめ
-
「最後の一手」から逆算する考え方は階段問題と同じ
-
今回の漸化式：
dp[i] = Math.min(dp[i-1] + a, dp[i-2] + b)