代码拉取完成,页面将自动刷新
# -*- coding: utf-8 -*-
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/8/19
# @File : D - Redistribution.py
#基础线性DP,redistribution。3,4 、 4,3 、 7
def dp_redistribution():#优化的方法,用前缀和思路
dp = [1] * (2000 + 1)
dp[1] = 0
dp[2] = 0
# 初始化
a = 0
for i in range(3, 2000 + 1):
a += dp[i - 3]
dp[i] = a % (10 ** 9 + 7)
return dp[s]
def dp_redistribution1():
dp = [1] * (2000 + 1)
dp[1] = 0
dp[2] = 0
# 初始化
for i in range(3, 2000 + 1):
dp[i] = (dp[i - 1] + dp[i - 3]) % (10 ** 9 + 7)
return dp[s]
"""
对于每一个n,可以由与n相差大于等于3的前面全部的方法数相加得到,dp[n] = dp[n-3]+dp[n-4]+dp[n-5]+……+dp[0],所以dp[0]设置为1
又因为dp[n-1] = dp[n-4]+dp[n-5]+dp[n-6]+……+dp[0]
所以dp[n] = dp[n-3] + dp[n-1] 状态转移方程
细节:必须用2000代替s才能ac。。。
"""
if __name__ == '__main__':
s = int(input())
res = dp_redistribution()
print(res % (10 ** 9 + 7))
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。