は

Question

問題が

「あなたは階段のケースを登っている。あなたが1つの段階または2つの段階を行うことができますいずれかのたびにあるこの動的計画クライミングのn-階段コードを説明してください。階段にn個の手順を実行します。どのように多くの異なる方法ですることができますあなたは階段を上りますか？ "

この問題のコード解決方法は次のとおりですが、わかりにくいです。誰が私に

int stairs(int n) { 
    if (n == 0) return 0; 
    int a = 1; 
    int b = 1; 
    for (int i = 1; i < n; i++) { 
    int c = a; 
    a = b; 
    b += c; 
    } 
    return b; 
} 

おかげで、

Answer 1

さて、まずあなたが再帰的な数式を理解する必要があり、そしてどのように我々はそれから、反復1を導出を説明することができます。

再帰式は：

f(n) = f(n-1) + f(n-2) 
f(0) = f(1) = 1 

（ - こうして加算一段階、二段階のためf(n-2)、および総数ためf(n-1)は、これらのオプションのいずれかを使用する方法の数です）。

これはよく知られているシリーズのfibonacci numbersであり、再帰を何度も再計算するのではなく、単純に各数値を計算しているので、はるかに効率的な解決方法が得られます。