【階段の上り方】階段の上り方

今回は paiza のDPで【階段の上り方】の最終問題に挑戦！

問題概要

入力： n a b c

• 階段の高さ n（段数）
• 一度に登れる段数 a 段・b 段・c 段（3種類、すべて異なる）

求めるもの：

• ちょうど n 段に到達する登り方の数

条件：

• 1 ≤ n ≤ 30
• 1 ≤ a, b, c ≤ 7
• a, b, c はすべて異なる

入力例：

10 2 3 4

出力例：

17

✅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, c] = lines[0].split(' ').map(Number);
    
    const dp = [];
    dp[0] = 1;
    
    for(let i = 1; i <= n; i++){
        dp[i] = 0;
        if (i >= a) dp[i] = dp[i] + (dp[i-a] || 0);
        if (i >= b) dp[i] = dp[i] + (dp[i-b] || 0);
        if (i >= c) dp[i] = dp[i] + (dp[i-c] || 0);
    }
    
    console.log(dp[n]);
});

こういう書き方もできるかも

dp[i] = (i >= a ? dp[i-a] : 0)
      + (i >= b ? dp[i-b] : 0)
      + (i >= c ? dp[i-c] : 0)

📝階段問題シリーズのまとめ

• 基本構造
  • 問題はすべて 「n段目に到達する方法の数」 を求める形式
  • 各段へ行くには 1歩の歩幅 a, b, c… を使う

• 共通のDP設計 状態定義
  • dp[i] = i段目に到達する方法の数
  • 初期条件dp[0] = 1（何もせず0段目にいる方法は1通り）
  • 到達不可能な場合も正しく0が出るようにする
  • 漸化式

dp[i] = 0;
if (i >= a) dp[i] = dp[i] + dp[i-a];
if (i >= b) dp[i] = dp[i] + dp[i-b];
if (i >= c) dp[i] = dp[i] + dp[i-c]; 

• 可視化のメリット
  • 木構造→ 分岐ごとにルートが見える（DFS的な視点）
  • DP表→ 実際のカウントの流れ・重複回避が一目でわかる 2つを照らし合わせると直感と数理が一致する

• 学んだポイント
  • DPは「過去の結果を使い回すことで再計算を避ける」
  • 配列を使うとわかりやすい、変数だけでも省メモリ実装可能
  • 漸化式さえ押さえれば、歩幅の種類や値を変えても同じパターンで解ける

僕の失敗談(´;ω;｀)と解決法🐈