You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Solution:
一开始想到了递归的办法，但是居然 TLE 了。想想也是，testcase 是44，每一步都有两种走法，复杂度为 O(2^N):
public class Solution
{
public int count = 0;
public int climbStairs(int n)
{
climbStairsHelper(n);
return count;
}
public void climbStairsHelper(int n)
{
if(n == 0)
count++;
else if(n < 2)
climbStairsHelper(n - 1);
else
{
climbStairsHelper(n - 2);
climbStairsHelper(n - 1);
}
}
}
在这里递归解法的问题就是当前递归较小规模的问题，会在后面较大规模的问题时重复求解小规模的问题，无法利用之前得到的结论。
看了 Discuss，这不是裴波那契数列么……
但要注意的是数列的开始并非1，1，2……，要根据题意有所改变，处理0级台阶（也就是说如果一共有n 级台阶要上，stage 的总数量应该是 n+1， 要包括第0级这种边界 case）：
0个台阶时有0种办法，
1个台阶时有1种办法，
2个台阶时有2种办法，
3个台阶后：
要到第3个台阶，需要先到第二个台阶，然后跨一级；
或者，需要先到第二个台阶，然后跨两级；
所以上第三级台阶的办法数就是上第二级的办法数+上第一级的办法数
……
以此类推。
