【在线编程产品介绍】

阿里云开发者社区在线编程：

免费刷题大神器，助你拿到好offer

周赛月赛不停歇，做题还能领奖品

大赛笔试全真题，常做常新有惊喜

点击链接开始产品体验：https://developer.aliyun.com/coding

本文为大家介绍的是“109.变化的字符”的解法探究。先来看一下题目内容：

题目详情

等级：困难
知识点：DP
查看题目：变化的字符

Tom又碰到了一道字符串的题目。

有一个字符串s(1<=|s|<=3e5，|s|为奇数)，这个字符串只包含0,1和字符'.'，这个'.'字符可以任意变为0或者1。

现在可以通过一些操作来缩短这个字符串，每次操作可以任意选择连续的三个字符，然后将这个连续的三个字符变成出现数量最多的那个字符(比如001变为0，101变为1，1.0可以变为0也可以变为1)。

通过更改字符'.'，问通过(|s|-1)/2次操作后最终这个字符串只剩下一个1的方案有多少种，答案对1e9+7取模。

输入一行字符串s

输出一个数表示方案数。
示例1
输入：
"1.0.1"
输出：
4

解题方法：

操作次数为，1.0.1长度为5就是可以操作2次。

分别可以把字符串变为10001 10011 11001 11011，这四种都可以使得最后只剩下1，所以答案为4种。

因为最后是剩下1所以我们肯定优先消去0，dp i,j,k的含义就是前i个字符中把第j个字符变成k 的方案数。

把所有数据处理一遍再求一遍最大值即可。

时间复杂度：O(24n)
空间复杂度：12n

看完之后是不是有了答题思路了呢，快来练练手吧：109.变化的字符

在线编程周赛、月赛火热进行中，更有限时答题活动，定制卫衣、双肩背包、机械键盘等多重好礼等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程3月份比赛正式开启！机械键盘等你拿！