100日アルゴリズム[4日目・動的計画法]

問題

https://leetcode.com/problems/climbing-stairs/description/

回答

function climbStairs(n: number): number {
    const dp:number[] = [...Array(n + 1)].map(() => 0)
    dp[0] = 1;
    dp[1] = 1;
    for (let i:number = 2; i<= n+1; i++) {
        dp[i] = dp[i-2] + dp[i-1]
    }
    return dp[n]
};

階段を1歩で登るか2歩で登るかを毎回選択し、n段目までに到達する組み合わせ回数を数えるアルゴリズムです。

まず、0段目に行くには1通り、1段目に行くには1通りなので、n＋１個分の要素をもつ配列の0番目と1番目のindexに1を格納しておきます。あとはfor文で2からスタートしn+1まで繰り返し処理を行い、1個前と2個前のindexの値から次のindexの組み合わせの個数を計算し、最後n段前に到達する時の組み合わせの数を返して終了です。

dp問題の解き方3通り

dp問題は、recursion、memoization、tabulationの３つのアプローチを使うことができます。上記の解き方はtabulationの解き方にあたります。