猴子爬山一只頑猴在一座有N級臺階的小山上爬山跳躍。上山時需從山腳至山頂往上跳N級臺階，一步可跳1級，或跳3級，求上山有多少種不同的跳法？ （N<50）

問題分析:

每一次都可以選擇1,2,3有3種跳法

方法1 直接使用遞歸

jumpWay = [1, 3]footstep = int(input())jumping = 0#first writedef jump(nowstep, footstep, jumpWay):if nowstep == footstep:global jumpingjumping += 1returnelif nowstep > footstep:returnelse:for i in range(len(jumpWay)):jump(nowstep + jumpWay[i], footstep, jumpWay)jump(0, footstep, jumpWay)

---

但是這種方式會提示 遞歸層數過多

想辦法對算法進行合理優化,排列組合

方法2 循環全排列

size = int(input())
n3 = size//3
res = 0# 求階乘
def jiecheng(n):num = 1if n==1:return 1else:for i in range(1,n+1):num*=ireturn num# 求排列        
def c43(n4,n3):# return jiecheng# 3!/(4-3)!*3!# j3 = jiecheng(3)return jiecheng(n4)//(jiecheng(n4-n3)*jiecheng(n3))# a32不用了
# def a32(n3,n2):
#    return jiecheng(n2)//jiecheng(n3)-jiecheng(n2)# 循環
for i in range(size+1):# i 為有幾個 1步的情況for j in range(n3+1):# j為有 幾個 3步的情況if (i+j*3) == size:# temp 為總數temp = j+ires+=c43(temp,j)
print(res)