leetcode70 climbing stairs 爬楼梯游戏

姘存按发布于2019-08-14 17:52 / 747人阅读

摘要：题目要求假设有级台阶为正整数，每次可以爬一级台阶或两级台阶。问有多少种方法爬完级台阶递归方法最后一步可以是一级台阶，或者是两级台阶，一共两种情况。

题目要求：假设有n级台阶（n为正整数），每次可以爬一级台阶或两级台阶。问有多少种方法爬完n级台阶？

递归方法
最后一步可以是一级台阶，或者是两级台阶，一共两种情况。可通过递归获得n-1级台阶和n-2级台阶的和获得n级台阶的结果
台阶数量过高的话，性能会很差

/**
 * @author rale
 * 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?
 * Note: Given n will be a positive integer.
 */
public class ClimbingStairs {

    //递归    
    public int climbStairs(int n) {
        if(n<=1){
            return 1;
        }
        if(n%2==0){
            return (int) (Math.pow(climbStairs(n/2), 2)+Math.pow(climbStairs(n/2-1), 2));
        }
        return climbStairs(n-1)+climbStairs(n-2);
    }
}

非递归情况
为了提高性能，将递归转化为循环
可以将题目转换为n级台阶中有几步是爬了两级台阶，几步是爬了一级台阶
例如 3级台阶的的场景为 3个一步或者 1个一步加1个两步
则n级台阶的场景为：
假设n级台阶中有a个两步，n-2*a个一步，则情况总数为C(n-a,a)
a的取值范围为[0,n/2]

/**
 * @author rale
 * 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?
 * Note: Given n will be a positive integer.
 */
public class ClimbingStairs {
        public int climbStairs(int n){
        if(n<=1){
            return 1;
        }
        int countTwo = 1;
        int total = 1;
        while(countTwo*2<=n){
            //此处应设为long，防止值溢出
            long temp = 1;
            for(int i = n-countTwo, j = 1 ; j<=countTwo; i--,j++){
                temp = temp*i/j;
            }
            total += temp;
            countTwo++;
        }
        return total;
    }
}

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

专线服务超融合服务器爬楼梯 Climbing Stairs 楼梯

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66852.html

LeetCode 之 JavaScript 解答第70题 —— 爬楼梯（Climbing Stair

摘要：小鹿题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。算法思路二种解决思路，第一利用递归第二利用动态规划。就是因为有了重复元素的计算，导致了时间复杂度成指数的增长。 Time：2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿题目：Climbing Stairs You a...

chemzqm 2019-08-23 16:55 评论0 收藏0
[Leetcode] Climbing Stairs 爬楼梯

摘要：递归法复杂度时间空间思路这题几乎就是求解斐波那契数列。最简单的方法就是递归。但重复计算时间复杂度高。代码递推法复杂度时间空间思路实际上我们求的时候只需要和的值，所以可以减少一些空间啊。 Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top. Each time you c...

tinyq 2019-08-14 12:26 评论0 收藏0
[leetcode] Climbing Stairs

摘要：实质就是把之前出现过的中间结果记录，下次再出现相同情况的时候，通过可以只用的时间复杂度得到。表示到达第层楼梯的不同走法。那么题目中每次可以选择走一步，或者两步，。从迭代公式可以知道，有两个，和。 70. Climbing Stairs You are climbing a staircase. It takes n steps to reach to the top.Each tim...

int64 2019-08-14 16:50 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
leetcode 746 Min Cost Climbing Stairs

摘要：同时你可以选择从第阶开始或者第一阶开始。我们的目标是找出你爬到最顶层所付出的最小的开销。最低开销是，从第阶开始，只花费就可以到顶层。想法动态规划问题。的长度应该为数组长度加一，其中数组的最后一个元素的值就是本题的答案，最低开销。题目详情 On a staircase, the i-th step has some non-negative cost cost[i] assigned ...

fyber 2019-08-16 11:01 评论0 收藏0