[数据结构与算法]牛客 DP61 串(python)

长度不超过nn，且包含子序列“us”的、只由小写字母构成的字符串有多少个？ 答案对10^9+710
9 +7取模。
所谓子序列，指一个字符串删除部分字符（也可以不删）得到的字符串。
例如，“unoacscc"包含子序列"us”，但"scscucu"则不包含子序列"us"

输入描述： 一个正整数n
输出描述： 一个正整数，为满足条件的字符串数量对10^9+7取模的值

此题只要能够写出状态转移方程就比较好写了
如果没有及时取余的话会导致超时
所以要在每次迭代的时候就及时做取余操作
状态中有三个参数：
$f[n]=[d{p}_1,d{p}_2,d{p}_3]$

• $d{p}_1$表示n位数字时，完全不含有u和s的字符串个数
• $d{p}_2$表示n位数字时，含有u但是不含有前u后s的字符串个数
• $d{p}_3$表示n位数字时，已经含有前u后s的字符串个数

转移公式如下表示：
$d{p}_3=d{p}_2+d{p}_3?26$
$d{p}_2=d{p}_1?25+d{p}_2$
$d{p}_1=d{p}_1?25$

用时和内存都排名很前面：

n = int(input())
def dfs(n):
    if n == 2:return 1
    dp = [25,1,0]#无u,有u无us，有us
    result = 0
    mod = 10**9+7
    for i in range(2,n+1):
        dp[2] = (dp[1]+dp[2]*26)%mod
        dp[1] = (dp[0]+dp[1]*25)%mod
        dp[0] = (dp[0]*25)%mod 
        result += dp[2]
    return result%mod
print(dfs(n))
    

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖