青蛙爬台阶问题的三种解法@python |
您所在的位置：网站首页 › 滑板怎么下载三阶台阶 › 青蛙爬台阶问题的三种解法@python |
青蛙爬台阶问题的三种解法@python
|
本文系原创，转载请注明出处 题意描述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? 青蛙跳台阶问题，一只青蛙要跳上n层高的台阶，一次能跳一级，也可以跳两级，请问这只青蛙有多少种跳上这个n层高台阶的方法？ 思路分析：这个问题有三种方法来解决，并在下面给出三处方法的python实现 方法1:递归设青蛙跳上n级台阶有f(n)种方法，把这n种方法分为两大类，第一种最后一次跳了一级台阶，这类方法共有f(n-1)种，第二种最后一次跳了两级台阶，这种方法共有f(n-2)种，则得出递推公式f(n)=f(n-1)+f(n-2),显然，f(1)=1,f(2)=2，递推公式如下： * 这种方法虽然代码简单，但效率低，会超出时间上限* 代码实现如下 class Solution: # @param {integer} n # @return {integer} def climbStairs(self, n): if n==1: return 1 elif n==2: return 2 else: return self.climbStairs(n-1)+self.climbStairs(n-2) 方法2: 用循环来代替递归这种方法的原理仍然基于上面的公式，但是用循环代替了递归，比上面的代码效率上有较大的提升，可以AC 代码实现如下： class Solution: # @param {integer} n # @return {integer} def climbStairs(self, n): if n==1 or n==2: return n a=1;b=2;c=3 for i in range(3,n+1): c=a+b;a=b;b=c return c 方法三：建立简单数学模型，利用组合数公式这种方法我比较喜欢 设青蛙跳上这n级台阶一共跳了z次，其中有x次是一次跳了两级，y次是一次跳了一级，则有z=x+y ,2x+y=n,对一个固定的x，利用组合可求出跳上这n级台阶的方法共有 python代码实现如下： class Solution: # @param {integer} n # @return {integer} def climbStairs(self, n): def fact(n): result=1 for i in range(1,n+1): result*=i return result total=0 for i in range(n/2+1): total+=fact(i+n-2*i)/fact(i)/fact(n-2*i) return total |
种方法 又因为 x在区间[0,n/2]内，所以我们只需要遍历这个区间内所有的整数，求出每个x对应的组合数累加到最后的结果即可【本文地址】
今日新闻 |
推荐新闻 |