Climbing Stairs

https://leetcode.com/PRoblems/climbing-stairs/

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?

(1)这道题其实是一道fibonacci数列题。当n=1时，f(n)=1;当n=2时，f(n)=2（有1+1,2这两种方式）;当n>=3时，有f(n)=f(n-1)+f(n-2)(2)但是实现时如果直接使用递归，就会超时，所以这里使用循环(3)用f0来记录f(n-2),用f1来记录f(n-1)，按照之前的公式f(n)=f(n-1)+f(n-2)，即得f2=f0+f1;然后更新f0和f1，使得这两个记录都往前移动一位，即f0=f1,f1=f2;一共进行n-1次，返回f2

public class Solution {    public int climbStairs(int n) {        int f0 = 1;        int f1 = 1;        int f2 = n;                n--;        while (n-- > 0) {            f2 = f0 + f1;            f0 = f1;            f1 = f2;        }                return f2;    }}

对于这道题，记得之前有本书提到过尾递归的思想，所以这里应用了一把尾递归，不过单就这道题看来，其实就跟循环的中心思想是一样的，都是记录做过的两个状态。

public class Solution {    public int climbStairsTail(int n, int acc, int acc2) {        if (n == 0) {            return acc;        }                return climbStairsTail(n - 1, acc2, acc + acc2);    }        public int climbStairs(int n) {        if (n == 0 || n == 1) {            return n;        }                return climbStairsTail(n, 1, 1);    }}