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)。
查看原帖
点赞 评论
相关推荐
联想公司氛围 241人发布 点赞 评论 收藏
分享
查看28道真题和解析 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 腾讯音乐求职进展汇总 #
78575次浏览 442人参与
# 入职第一天，你准备什么时候下班 #
37703次浏览 241人参与
# 招行数字金融训练营 #
76092次浏览 337人参与
# 牛友故事会 #
435081次浏览 10435人参与
# 入职第四天，心情怎么样 #
22955次浏览 342人参与
# 你的办公桌上都有什么？ #
3949次浏览 34人参与
# 腾讯云智研发2025实习生招聘 #
105333次浏览 1275人参与
# 阿里云工作体验 #
18073次浏览 84人参与
# 你的工资什么时候发？ #
21630次浏览 175人参与
# 小红书工作体验 #
44038次浏览 394人参与
# 海康威视求职进展汇总 #
448839次浏览 3499人参与
# 硬件应届生薪资是否普遍偏低？ #
64832次浏览 492人参与
# 这些公司卡简历很严格 #
22661次浏览 91人参与
# 同程旅行工作体验 #
3233次浏览 20人参与
# 职场破防瞬间 #
37396次浏览 512人参与
# 机械人，说说你的烦心事 #
54881次浏览 767人参与
# 元戎启行求职进展汇总 #
27352次浏览 205人参与
# 实习必须要去大厂吗？ #
77906次浏览 1157人参与
# Offer比较，求稳定还是求发展 #
34430次浏览 201人参与
# 硬件人的春招flag #
36864次浏览 395人参与
# 米哈游工作体验 #
7828次浏览 72人参与
# TP-LINK工作体验 #
42154次浏览 806人参与