投篮得1分,远距离投篮得2分,但他由于他技术有限,不能连续3次远距离投篮,问小明成功得n分的方案数。
输入格式:
一行,一个数字,表示n。
输出格式:
输出造成n点伤害的方案总数。
投篮得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)
如有帮助,请点击我的回答下方的【采纳该答案】按钮帮忙采纳下,谢谢!