主題
題目連結(jié)：
題目意譯：
你被給定一個(gè)索引值從 0 開(kāi)始數(shù)且長(zhǎng)度為 n 的二元字串 s，而你可以在上面執(zhí)行以下兩種操作：
選擇一個(gè)索引值 i 並翻轉(zhuǎn)索引值 0（含）到索引值 i（含）的所有字元，其成本為 i + 1、
選擇一個(gè)索引值 i 並翻轉(zhuǎn)索引值 i（含）到索引值 n - 1（含）的所有字元，其成本為 n - i。
回傳讓所有字元變?yōu)橐粯拥淖钌偎璩杀尽?/div>
翻轉(zhuǎn)一個(gè)字元代表著其值將從 '0' 變成 '1' 或是從 '1' 變成 '0'。
限制：
1 ≦ s.length == n ≦ 10 ^ 5
s[i] 只會(huì)是 '0' 或是 '1'
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： s = "0011"
輸出： 2
解釋： 套用第二個(gè)操作且 i = 2 來(lái)得到 s = "0000"，其成本為 2?？梢宰C明 2 為將所有字元變?yōu)橐粯拥淖钌偎璩杀尽?/div>
範(fàn)例 2：
輸入： s = "010101"
輸出： 9
解釋： 套用第一個(gè)操作且 i = 2 來(lái)得到 s = "101101"，其成本為 3。
套用第一個(gè)操作且 i = 1 來(lái)得到 s = "011101"，其成本為 2。
套用第一個(gè)操作且 i = 0 來(lái)得到 s = "111101"，其成本為 1。
套用第二個(gè)操作且 i = 4 來(lái)得到 s = "111110"，其成本為 2。
套用第二個(gè)操作且 i = 5 來(lái)得到 s = "111111"，其成本為 1。
將所有字元變成一樣的總成本為 9。可以證明 9 為將所有字元變?yōu)橐粯拥淖钌偎璩杀尽?/div>
解題思維：
首先，我們可以看到最佳解一定不存在著兩個(gè)索引值 i 、 j（i < j）使得：
索引值 i 使用的是第二個(gè)操作、而索引值 j 使用的則是第一個(gè)操作。
因?yàn)槿绻嬖诘脑?，s[i] 和 s[j] 不可能會(huì)一樣。
因此我們可以把問(wèn)題拆成「左到右」和「右到左」兩個(gè)方向。前者固定使用第一個(gè)操作、而後者則固定用第二個(gè)操作。最後再窮舉「分界點(diǎn)」即可。
而對(duì)於「左到右」可以用類似前綴和（Prefix Sums）的方式計(jì)算從 s[0] ~ s[i] 只使用第一個(gè)操作最少所需之操作。
定義一個(gè)二維陣列 P，其中 P[i][j] 代表著 s[0] ～ s[i] 所有字元統(tǒng)一變成 j（j = 0 或是 1）的最少所需操作數(shù)?？梢钥吹竭f迴式為：
P[0][0] = (s[0] == '0')、
P[0][1] = (s[0] == '1')、
當(dāng) i > 0 且 s[i] == '0' 時(shí)，P[i][0] = P[i - 1][0]、
當(dāng) i > 0 且 s[i] == '0' 時(shí)，P[i][1] = P[i - 1][0] + (i + 1)、
當(dāng) i > 0 且 s[i] == '1' 時(shí)，P[i][0] = P[i - 1][1] + (i + 1)、
當(dāng) i > 0 且 s[i] == '1' 時(shí)，P[i][1] = P[i - 1][1]。
因此從左至右算出每一個(gè)位置的 P[i][0] 和 P[i][1] 之值之後，便可以對(duì)「右到左」這個(gè)方向做類似的事情（設(shè)其為 S[i][j]，代表著從 s[i] ～ 字串結(jié)尾統(tǒng)一變成 j 的最少次數(shù)）。
最後我們便可以窮舉「分界點(diǎn)」，也就是說(shuō)以索引值 i 為界，s[0] ~ s[i] 只使用第一個(gè)操作、而 s[i + 1] ～ 字串結(jié)尾則使用第二個(gè)操作。
可以看到對(duì)於索引值 i 來(lái)說(shuō)，其所需次數(shù)將會(huì)是 P[i][0] + S[i + 1][0] 和 P[i][1] + S[i + 1][1] 兩者的最小值（如果 i + 1 不存在則視為 0）。記得考慮只使用第二個(gè)操作的情況，即 S[0][0] 和 s[0][1]。
而所有索引值所需次數(shù)的最小值即為所求。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
創(chuàng)作回應(yīng)
