【線上程式設計産品介紹】
阿裡雲開發者社群線上程式設計：
免費刷題大神器，助你拿到好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月份比賽正式開啟！機械鍵盤等你拿！