Python爬楼梯算法

投篮得1分，远距离投篮得2分，但他由于他技术有限，不能连续3次远距离投篮，问小明成功得n分的方案数。

输入格式:
一行，一个数字，表示n。

输出格式:
输出造成n点伤害的方案总数。

这题目用动态规划都不行, 只能从结果上找规律,直接推算了,时间复杂度O(n)
规律是前面30个值为1,2,3,5,8,12,19,30,47,74,116,182,286,449,705,1107,1738,2729,4285,6728,10564,16587,26044,40893,64208,100816,158296,248548,390257,612761
前面2个值为1,2,
第3到5个值为前面两个值之和,
第6到7个值为前面两个值之和减1.
第7个之后的值为前面两个值之和减前面第7个值

n = int(input("请输入一个整数n："))
def pf(n):
    if n<=0:
        return 0
    res = [1,2]
    for i in range(2,n):
        if i < 5:
            t = 0
        elif i < 7:
            t = 1
        else:
            t = res[i-7]
        res.append(res[i-1]+res[i-2]-t)
    return res[n-1]

count = pf(n)
print(n,"点伤害的方案总数:",count)

如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!

你这个题目复杂度太高，n的值不能太大，如果你要求2秒之内的话，我这个程序只能支持n到35左右，再大了就不行了

n = int(input())
def dg(n,status):
    if n==1:
        return 1
    elif n==2:
        if status<2:
            return 2
        else:
            return 1
    else:
        if status<2:
            status+=1
            return dg(n-1, 0) + dg(n-2, status)    
        else:
            return dg(n-1, 0)
print(dg(n,0))