【在線編程產品介紹】
阿里雲開發者社區在線編程：
免費刷題大神器，助你拿到好offer
周賽月賽不停歇，做題還能領獎品
大賽筆試全真題，常做常新有驚喜
點擊鏈接開始產品體驗：https://developer.aliyun.com/coding
本文為大家介紹的是“109.變化的字符”的解法探究。先來看一下題目內容：
題目詳情
查看題目：109.變化的字符 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月份比賽正式開啟！機械鍵盤等你拿！
