但问题是
你攀登楼梯的情况下,每次可以使1级或2级的楼梯有n个步骤。在有多少不同的方式你能爬上楼梯?
"You are climbing a stair case. Each time you can either make 1 step or 2 steps. The staircase has n steps. In how many distinct ways can you climb the staircase?"
以下是此问题的code解决方案,但我无法理解它。任何人都可以解释我
Following is the code solution for this problem but I am having trouble understanding it. Can anybody explain me
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;
}
谢谢
嗯,首先你需要了解递推公式,以及如何从中获得迭代之一。
Well, first you need to understand the recursive formula, and how we derived the iterative one from it.
的递推公式是:
f(n) = f(n-1) + f(n-2)
f(0) = f(1) = 1
( F(N-1)
的一步, F(N-2)
的两个步骤,总人数是如何使用这些选项中的一个数字。 - 这样的总和)
(f(n-1)
for one step, f(n-2)
for two steps, and the total numbers is the number of ways to use one of these options - thus the summation).
如果你仔细观察 - 这也是一个众所周知的系列 - 斐波那契数和解决的方法就是计算每个数字BUTTOM行动,而不是重新计算一次递归遍地,从而更有效的解决方案。
If you look carefully - this is also a well known series - the fibonacci numbers, and the solution is simply calculating each number buttom-up instead of re-calculating the recursion over and over again, resulting in much more efficient solution.