1、数学思路
题目要求限制只能走1阶或2阶,2阶可以替换成两个1阶;从可能性上看具体步法罗列出来就是 :
100个1阶+0个2阶 C100/0
98个1阶+1个2阶 C99/1
96个1阶+2个2阶 C98/2
... ...
2个1阶+49个2阶 C51/49
0个1阶+50个2阶 C50/50
然后每一个方式,又有多种组合步法交织可行,依据中学的排列组合就有了后面的 Cm/n 的组合数
总和= C100/0 + C99/1 + C98/2 + ... ... + C51/49 + C50/50。
需要使用Math工具,时间复杂度O(n)。
此解法需要数学基础来联系起来,利用数学公式提高计算效率。实测100阶的步法结果是: 573147844013817084101 ,暴力方法计算需要很长时间。
定理也是经过 分析---归纳---证明 的淬炼,可拿来主义帮我们提高计算效率;类似等差数列求和公式,一步加减法即可求解。
2、逻辑思路
分析逻辑就是将复杂的应用题转化为计算机可执行的步骤,计算机最擅长就是明确的重复计算;
试想最后到100阶的一步,可以是跨2阶到达也可以是跨1阶到达的,对应的前面是走过98阶和走过99阶的两种情况;若前面的98或99阶步法能明确,答案就可出来:
f(100) = f(99) + f(98) 推演=> f(n) = f(n-1) + f(n-2)
归纳:
f(1) = 1, f(2) = 2(2阶有两个走法), 初验 f(3) = f(2) + f(1) = 2+1 =3 符合预期,
故可以使用递归法将无法计算的量级回归到可手算量级即可,不一定是从 f(1)和f(2)开始,如下:
- if n==3:
- return 3
- elif n==4:
- return 5
继续分析:
f(4) = f(3) + f(2)
f(5) = f(4) + f(3) = [ f(3) + f(2) ] + f(3)
注:分解步骤发现会出现大量重复计算,导致100阶无法计算出结果,故需增加缓存
- cached= [0] * 101 // 减少重复计算,极大提高效率
-
- def stepCount(n):
- if cached[n]>0:
- return cached[n]
- print(n)
- if n==1 or n==2:
- return n
- else:
- cached[n] = stepCount(n-2) + stepCount(n-1)
- return cached[n]
-
- if __name__ == "__main__":
- print(stepCount(100))
输出结果:
100
98
96
...
6
4
2
3
1
2
5
7
...
95
97
99
573147844013817084101
输出的先偶数后奇数,可以看出递归压栈出栈的过程,更重要的看出缓存生效了。