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)。
相关推荐
投递华勤技术等公司10个岗位
11-04 22:03
武汉理工大学 Java 
菜菜菜小白菜菜菜：我在字节实习了四个月，有转正的压力所以周末大部分也在公司自学，也是因为一些原因转正拖的很久，这个点还没答辩，过段时间才回去答辩。整个不确定性的焦虑贯穿了我的秋招三个月，我也曾经犹豫过是不是应该放弃转正走秋招更快，最后因为沉没成本一直舍不得放弃，前前后后七个月真的挺累的，尤其是没有来字节实习的同学已经校招拿到意向时更加焦虑。这段时间也跟mentor聊了很多次，他告诉我未来工作上或者生活上，比这些更头疼的事情会更多，关键还是要调整好自己的心态。转正没有通过从过程上来看其实跟你自身没太大的关系，拖了三个月不出结果显然是ld的问题，并且今年美团最近的开奖大家似乎都不是很乐观，所以不去也罢。我在字节实习的时候，6月份有一个赶上春招末期的25届同事刚面进来，也拿到了小sp的薪水。不要对这件事有太大的压力，时代的问题罢了 点赞 评论 收藏
分享