爬楼梯问题

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

此问题反应了斐波那契数列的一个应用。

状态转移方程为f(x) = f(x-1)+f(x-2)

用递归解决此题，发现时间超限。因为递归会不断进栈出栈。

    int climbStairs(int n)
    {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; i++)
        {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

迭代方法，也是递归和动态规划的一种，只用了3个变量的滚动数组。性能提升。

爬楼梯问题

原文：https://www.cnblogs.com/qianxinn/p/14622681.html