70. 爬楼梯

思路1：递归回溯（超时）

调用链比较深，还需要回溯，用时比较久，不推荐

class Solution {
    int res=0;
    public int climbStairs(int n) {
        getStep(n);
        return res;
    }

    private void getStep(int n) {
        if (n<=1){
            res++;
        }else if (n>=2){
            n-=2;
            getStep(n);
            n+=1;
            getStep(n);
        }
    }
}

思路2：动态规划

思路：

由于我们现在占的台阶可以从前一步跳上来也可以从前两步跳上来，因此有
- f(x)=f(x−1)+f(x−2)
- 这种有明显公式，下一步的结果由上一步决定的一般用动态规划都比较快

- 设r为当前点，q，p为前两个点，则有

代码：

public int climbStairs(int n) {
            //由于我们现在占的台阶可以从前一步跳上来也可以从前两步跳上来，因此有
            // f(x)=f(x−1)+f(x−2)
            //这种下一步的结果由上一步决定的一般用动态规划都比较快
            // 设r为当前点，q，p为前两个点，则有
            int q = 0, p = 0, r = 1;
            for (int i = 1; i <= n; i++) {
                q = p;
                p = r;
                r = q + p;
            }
            return r;
        }