AI牛可乐
2023-09-22 19:37 带#牛客在线求职答疑中心#提问都会召唤我
关注
这个问题可以通过动态规划来解决。首先，我们需要定义状态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)。
查看原帖
点赞 评论
相关推荐
05-23 20:59
湖南工商大学 测试开发 
影中藏刀：看得出你准备的真的很少，不过去年在这个时候我还在学ssm呢，比我要好得多呢，肯定有机会的呢，努力成为八股文战神吧
投递数字马力等公司7个岗位 点赞 评论 收藏
分享
算法太卷啦
牛客热帖
更多
正在热议
更多
# 26届的你们有几段实习？ #
40497次浏览 459人参与
# 月薪多少能在一线城市生存 #
23409次浏览 277人参与
# 你后悔自己读研吗？ #
18067次浏览 233人参与
# 你以为的实习VS真实的实习 #
25542次浏览 239人参与
# 当下环境，你会继续卷互联网，还是看其他行业机会 #
117348次浏览 810人参与
# 打工人的工作餐日常 #
51968次浏览 407人参与
# 双非能在秋招上岸吗？ #
221109次浏览 1170人参与
# 你觉得早上几点上班合适？ #
71594次浏览 299人参与
# 一人推荐一个值得去的通信/硬件公司 #
186032次浏览 1858人参与
# 你认为哪些项目算烂大街？ #
16537次浏览 265人参与
# 哪些公司真双非友好？ #
15229次浏览 81人参与
# 追觅科技求职进展汇总 #
17892次浏览 120人参与
# 机械校招之路总结 #
93648次浏览 1893人参与
# 你被哪些公司秒挂过？ #
30230次浏览 238人参与
# 找工作时的取与舍 #
82739次浏览 590人参与
# 秋招拿一个offer可以躺平吗 #
146131次浏览 940人参与
# 最难的技术面是哪家公司？ #
9166次浏览 73人参与
# 网申一定要掌握的小技巧 #
10809次浏览 66人参与
# 你觉得技术面多长时间合理？ #
98949次浏览 716人参与
# 如何KTV领导 #
62469次浏览 472人参与