首页 > 其他 > 详细

爬楼梯问题

时间:2021-04-06 20:42:41      阅读:19      评论:0      收藏:0      [点我收藏+]

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!