N楼梯台阶

Question

Bilbo在他朋友的位置，有N个台阶。比尔博是一位有思想的人，他想知道如果他每次只需要1或2步就能到达第N级楼梯的方式有多少。请注意，他不能 一次需要连续2个或2个以上的步骤。到达第N楼梯的 的一种方式与另一种方式不同，如果他触摸至少 一个不同的楼梯。

这是我的代码到目前为止，我无法弄清楚如何不允许连续两次采取两个步骤。帮帮我？

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

我假设你的问题是对连续两步移动的限制。问题要求函数知道一个状态信息：上一步（如果有）是两步？只需在参数列表中包含一个布尔标志。

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

这会不会阻止你的思路？

编辑验收

后，我加入了if语句使应用程序明确。