【在线编程产品介绍】
阿里云开发者社区在线编程：
免费刷题大神器，助你拿到好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月份比赛正式开启！机械键盘等你拿！
