总结:字符串子序列dp问题

问题一:统计字符串A中有多少个子序列 = 字符串 B

令dp(i , j) 为字符串A前i位,有多少个子序列 = B的前j位.

假设 B = XXLL

那么dp[i][1] 代表 子序列 "X"的个数

dp[i][2] 代表 子序列 "XX"的个数

dp[i][3] 代表 子序列 "XXL"的个数

dp[i][4] 代表 子序列 "XXLL"的个数

递推也很显然: XXLL 形成的条件是:  第i位为"L"且 1 ~ i - 1 中存在子序列 XXL

dp[i][j] = dp[i - 1][j]  //  当 A[i] != B[j]

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]  //  当 A[i] = B[j]

问题二:你可以修改字符,使得字符串A中不存在子序列 = 字符串 B 的最小修改次数.

其实跟上面意思一样,这里就是求一个最优化。

利用自顶向下的方式,递归的去解决这个问题。

令dp[i][j]为A字符串前i个,使得不存在前j的B字符串的最少修改次数。

dp[i][j] = dp[i - 1][j]  //  当 A[i] != B[j]

dp[i][j] = min(dp[i - 1][j - 1] + 1 , dp[i - 1][j - 1] ) //  当 A[i] = B[j] , 就是改或不改。

改的话,就往前。不改,那么就要求前i - 1 个数不存在 前j个B字符串。

还要注意到,给定的i, dp[i] 数组是非上升的。 因为限制条件越严格.

问题三:统计字符串中有多少个不同的字符串子序列

如果没有本质不同的限制 ,那么转移为 dp(i , j ) = dp(i - 1 , j) + dp(i - 1, j - 1).

有了本质不同。考虑当前一个以字母a结尾的长度为j的字符串集合.

....a

....a

.....a   

那么当现在又遇到一个字母a,求它的长度为j的子序列的个数时,重复的部分就是之前以字母a结尾的长度为j的字符串个数   容斥掉这个部分即可。

答案就是 dp[n][1] + ... + dp[n][n]

全部评论

相关推荐

2025-12-28 16:32
重庆邮电大学 Java
程序员花海:1.技能放最后,来面试默认你都会,技能没啥用 2.实习写的看起来没啥含金量,多读读部门文档,包装下 接LLM这个没含金量 也不要用重构这种 不会给实习生做的 3.抽奖这个还是Demo项目,实际在公司里面要考虑策略,满减,触发点,触发规则 库存 之类的,不是这个项目这么简单 4.教育背景提前,格式为 教育背景 实习 项目 技能 自我评价
简历被挂麻了,求建议
点赞 评论 收藏
分享
昨天 00:12
已编辑
香港大学 Java
这里没熟人,吐槽一下吧,楼主语文不太好,语句可能不太通顺,想到哪说到哪。我只想说字节,你太狠了。。。作为一个校招生,字节landing实在是地狱级别,来到字节已经一个月了,在这一个月里,每天都承受着巨大的压力,每天起床感觉胸闷气短,饭也吃不下,一个月已经瘦了五六斤了(也算是变相减肥了),一想到上班就莫名其妙地喘不过气来,闭上眼脑子里都是代码。压力一方面来自于mt的压力,一方面是自己的压力。我参与的项目是几个月的新项目,项目很多不完善的地方,业务流程不完善,很多代码需要根据做产品的需求做大改动,而楼主从来没有做过业务方面的编码,所以在理解业务需求的时候,非常难受,而且业务线很长,作为承接上下游的中间系统,不仅要了解自己项目的流程,还要了解上下游的流程,导致上手非常困难,也有可能是楼主太菜了QAQ。。楼主12.17入职,一周之内就已经开始做需求了,第一个需求就是新增和修改数据,mt美名其曰给我练手,但是一个小小的新增和修改涉及了太多细节,在字段定义不明确、数据来源不了解、处理流程不清晰的情况下,楼主花了一周时间完成了这个需求,当然做技术方案评审的时候,被吊了好几次,修改了几版方案。需求做完,被测试找出来十几个缺陷,每天不是在修bug,就是在修bug的路上,修bug修的精疲力尽,每天自测都需要花费很长时间,导致lz每天都十分紧张,不敢打开飞书,生怕又收到QA的信息,并且产品设计及其粗糙,很多地方都需要再三确认,严重拖慢进度。好不容易做完还被嫌进度太慢,下一个需求就让我开天辟地,完成整个业务流程的编码,lz真的直冒汗啊啊啊,真把我当老员工对待啊。最重要的一点,mt从来不给正反馈,每次问问题都会被反问,这个流程你真的理解了么,这个需求你认真思考了么,站在用户角度思考了么,站在产品角度思考了么,站在前端角度思考了么,站在QA角度思考了么,总之得不到什么有用的回复,每次问问题都是煎熬,从来得不到肯定的回复,要不就是反问,要不就是让lz去问产品,去和其他人对齐,每次都不被肯定的滋味真的很难受,导致lz现在不敢问问题,生怕再被吊,真的难受啊啊。顺便说一嘴,字节的福利是真的好,饭菜也很好吃(虽然我不大能吃得下)。今天11点刚到家,洗漱完上床已经快12点了,今天先写到这里吧,给自己留半小时抖音时间,毕竟只有睡前的时间是属于自己的。世界是个巨大的围城,有人想进来,有人想出去,不正真体验过不知道自己想要的到底是什么。。加油吧。
喵_coding:唉 进不去的挤破头都想进去 进去了的又真觉得很累 这个世界究竟怎么了
工作压力大怎么缓解
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务