数据结构&算法之--《N阶台阶的走法》

题目大概是这样的：有N阶台阶，你可以一次走1步，也可以一次走2步，问一共有多少种走法？

这种题一开始看起来好无头绪，其实大部分都可以用大事化小，小事化了的办法解决。先来说最常用的递归的解决方法：

1. N = 1时，只能1步走到，一共只有1种走法
2. N = 2时，可以走两个1步走到，也可以走一个2步走到，一共有2种走法
3. N > 2的时候，不管N是几，我们来想一下我们怎么走上最后一个台阶？答案很简单，1步走上去，或者2步走上去；这里用f(n-1)表示到第n-1个台阶的走法，f(n-2)表示到第n-2个台阶的走法，那么f(n) = f(n-1) + f(n-2)

用递归来解决很简单：

- (NSInteger)f:(NSInteger)n {
    if (n <= 2) {
        return n;
    }

    return [self f:(n-1)] + [self f:(n-2)]
}

使用递归，代码结构逻辑清晰，当然也有递归固有的缺点，维护函数调用栈，内存的开销都很大。
另外解决的办法就是使用普通的循环来解决。
循环处理的思想也和递归一样，就是f(n) = f(n - 1) + f(n - 2)，不同的是我们要把从f(1）..... f(n)的每个台阶的走法累加起来。

- (NSInteger)f:(NSInteger)n {
  if (n <= 2) {
    return n;
  }

  NSInteger first = 1;         // 代表第i-2个台阶的走法，这里i初始值为3，first初始值就是第一个台阶的走法，也就是1
  NSInteger seconde = 2; // 代表第i-1个台阶的走法，同上，初始值是第2个台阶的走法，也就是2
  NSInteger sumi = 0;        // 代表到第i个台阶的所有走法

  for (NSInteger i=3; i<=n; i++) {
      sumi = first + second;
      first = second;
      second = sumi;
  }

  return sumi;
}