algorithm - 如果您一次使用 1 个或 2 个，您可以攀爬的方式数

Question

我接受了面试，并被问到以下问题：

给定 n 个楼梯，如果你一次使用 1 个或 2 个，你可以爬多少种方式？

我认为递归可能有用吗？..还有其他方法吗？

Answer 1

将 L(N) 视为到达第 N 步的方法数。

由于您只有两个步骤可以到达那里：N-1 和 N-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; 
}
}