N階段ステップ

Question

ビルボは友人の場所にあり、N個のステップがあります。 Bilboは、 の思いやりのある人で、一度に1,2ステップを取ると、どのくらい多くの方法で彼が N階段に達することができるかを知りたがっていました。 は2回以上連続して2回以上取ることはできません。 のN番目の階段に達する方法の1つが、異なる階段を少なくとも に触れると、別の階段に到達します。

ここまでは私のコードです。私は2つのステップを2回続けて行かせることを許さない方法を考え出すことはできません。助けて？

public static int fibOptimized(int n) { 
    int arr[] = new int[n + 1]; 
    for (int i = 0; i < arr.length; i++) { 
     arr[i] = -1; 
    } 
    int output = fibHelper(n, arr); 
    return output; 
} 

public static int fibHelper(int n, int[] arr) { 
    if (n == 0) { 
     return 0; 
    } 
    if (n == 1) { 
     return 1; 
    } 
    if (arr[n] > -1) { 
     return arr[n]; 
    } 
    arr[n] = fibHelper(n - 1, arr) + fibHelper(n - 2, arr); 
    return arr[n]; 
} 

Answer 1

あなたの問題は、連続する2ステップ移動に対する制約であるとします。この問題は、関数がステータス情報の1ビットを知っていることを必要とします。前のステップ（あれば）は2ステップですか？パラメータリストにブール値フラグを含めるだけです。

int count_path(N, two_step) { 
    ... 
    count += count_path(N-1, false) 
    if not two_step 
     count += count_path(N-2, true) 

はその思考のあなたの列車をアンブロックするのでしょうか？承諾

AFTER

EDIT私は、アプリケーションを明確にするためにifのステートメントを追加しました。