2023-09-22 19:36 福州大学 C++
关注
#牛客在线求职答疑中心# 空字符串s。有以下两种操作：
1.将任意一个字母添加在s的末尾。
2.选择s的一个长度不小于2的连续子串， 复制下来添加到s的末尾。
小红希望用空串s生成一个给定的字符串t， 她想知道有多少种不同的生成方式? 由于答案可能过大， 请对10⁹+7 取模。
1.将任意一个字母添加在s的末尾。
2.选择s的一个长度不小于2的连续子串， 复制下来添加到s的末尾。
小红希望用空串s生成一个给定的字符串t， 她想知道有多少种不同的生成方式? 由于答案可能过大， 请对10⁹+7 取模。
全部评论
AI牛可乐
带#牛客在线求职答疑中心#提问都会召唤我
这个问题可以通过动态规划来解决。首先，我们需要定义状态dp[i][j]，表示生成字符串t的前i个字符，且最后一个字符是j的方案数。
初始状态为dp[0][j] = 1，表示生成空字符串的方案数为1。
状态转移方程为：
dp[i][j] = sum(dp[i-1][k])，其中k是j的前一个字母。
dp[i][j] = sum(dp[i-1][k])，其中k是j的前两个字母。
最后，答案为dp[n][t]，其中n是字符串t的长度，t是字符串t的最后一个字符。
时间复杂度为O(n^2)，空间复杂度为O(n)。
相关推荐
点赞 评论 收藏
分享
06-23 11:43
门头沟学院 Java 点赞 评论 收藏
分享
07-31 17:07
湘潭大学 嵌入式工程师 
DKS233：项目写太简单了，你用什么技术实现了什么功能，优化了多少，分了哪些模块，解决了哪些难点，最好分模块写，你写的太模糊了。精通还是少用吧，你确定问你底层你扛的住吗，最好用熟悉。具备良好**意识，这种空话不要写，技能层面，要写就写实在的，比如“熟悉常用数据结构，如，堆，栈，链表，哈希表，平衡树”这种 点赞 评论 收藏
分享
08-05 17:07
门头沟学院 硬件开发 
职场水母：大多数本科生都在急着谈恋爱吧，能上牛客的少之又少，倒是硕士在这里有很多，这部分人群走的路及其相似，当年都选择了考研，到现在找工作都喜欢上牛客，不得不说还是挺有远见的大家
。大家都是有远见的牛马 点赞 评论 收藏
分享