algorithm - 一度に 1 つまたは 2 つのいずれかを使用した場合、いくつの方法で登ることができますか

Question

面接を受け、以下の質問をされました。

n 個の階段がある場合、一度に 1 つまたは 2 つの階段を使用すると、いくつの方法で登ることができますか?

再帰が役に立つと思いますか?..他の方法はありますか?

Answer 1

L(N) を N 番目のステップに到達する方法の数と見なします。

N-1とN-2の2段しかないので

ステップに到達するすべての方法 (N-1) + ステップに到達する方法の数 (N-2) により、合計の方法数が得られます。

L(n) = L(n-1) + L(n-2)

そして、これはフィボナッチ数列のように見えます!

Answer 2

動的プログラミング コードを使用できます。

int ways(int n) {
int[] dp = new int[n+1];
Arrays.fill(dp, -1);
return go(0, dp, n); 
}

int go(int step, int[] dp, n) {
if(step == n) {
    return 1;
} else if(step>n) {
    return 0;
} else if(dp[step] != -1) {
    return dp[step];
} else {`enter code here`
    int ways = go(step+1, dp, n) + go(step+2, dp, n);
    dp[step] = ways;
    return ways; 
}
}