標(biāo)題說明

打印奇怪的打印機(jī)時，請遵守以下兩個特殊條件：

一次只能打印由相同字符組成的連續(xù)序列。

給定一個只包含小寫字母的字符串，你的任務(wù)是計算用該打印機(jī)打印出這個字符串所需的最少打印次數(shù)。字符串長度不超過100。

樣例

Example 1:

輸入: "aaabbb"

輸出: 2

說明: 先打印"aaa"，再打印"bbb"。

Example 2:

輸入: "aba"

輸出: 2

說明: 先打印"aaa"，再在中間的位置打印"b"覆蓋之前的”a”。

解題思路

參考程序

Ⅰ. 一個簡單的想法是，給出的字符串有幾段不同的字符，就打印幾次，不考慮打印覆蓋的情況。比如aabbc，那就打印三次。這是一種貪心策略，但是在某些情況下不能取得最優(yōu)解，比如aabba，我們先打印aaaaa，然后打印bb，只需要兩次。

Ⅱ. 那么搜索可行嗎？我們每次搜索起點(diǎn)在最左邊的打印區(qū)間（需要搜索終點(diǎn)），我們發(fā)現(xiàn)通過記錄目前正確打印到了哪個位置，我們可以直接求的下一次打印的起點(diǎn)。因?yàn)槲覀兛傂枰獜牡谝粋€出錯的位置開始打印。這樣做是可行的，但是復(fù)雜度是指數(shù)級別，仍有優(yōu)化的可能性。

Ⅲ. 結(jié)合之前兩種思路，我們來觀察總結(jié)一下，打印出來的字符串的特點(diǎn)：

假設(shè)某一次打印機(jī)打印了若干個'a'，像這樣：”aaaaaa”，在這之后打印的字符，無非是三種情況：

● 在這段字符串的內(nèi)部打印，但是不覆蓋這段字符串的一端，例如”abbbaa”、”abbada”。

● 在這段字符串的外部打印，完全不覆蓋這段字符串，例如”bbaaaaaa”、”bbaaaaaaccc”。

● 覆蓋這段字符串的一端，例如”baaaaa”、”baaacccccc”。

上面所說的第三種情況，看起來就像后來的字符都打印在”a”組成的字符串的外部。事實(shí)上，如果打印了一串字符串后，再打印一些字符覆蓋這段字符串的端點(diǎn)會造成浪費(fèi)，也就是說被覆蓋的這字符串的部分一開始完全沒有必要打印，也不會對最終打印次數(shù)造成影響。所以，我們可以假定，打印時不存在浪費(fèi)，也就是說某次打印可以覆蓋前面某一次打印的（不包含端點(diǎn)的）內(nèi)部，也可以不覆蓋，但是不能覆蓋前面某一次打印的端點(diǎn)。

Ⅳ. 對于一個已知的目標(biāo)字符串s，我們考慮打印出這個字符串最左邊的字符s[0]的那次打印，我們總可以在打印方案中，把該次打印放到第一次打印。可以這樣做的理由是，由于c中的假定，其它的打印要么在這次打印的內(nèi)部（不包含端點(diǎn)），要么在這次打印的外部，并且由于包含目標(biāo)字符串的最左端點(diǎn)，所以這次打印也不可能在別的打印的內(nèi)部。這樣一來我們就可以枚舉包含s[0]的那次打印的長度L，然后把原目標(biāo)字符串分為s[0 ~ L-1]和s[L ~ N-1]（設(shè)原字符串長度為N），其中，由a中的假定可知s[0]==s[L-1]必須成立（因?yàn)槎它c(diǎn)不被覆蓋）。s[0 ~ L-1]的最少打印次數(shù)實(shí)際等于 s[1 ~ L-1]的最少打印次數(shù)（也等于s[0 ~ L-2]的最少打印次數(shù)），這是因?yàn)榇蛴〕銎渲幸粋€字符串的打印方案可以稍加變動變成另一個的打印方案而不改變打印次數(shù)（讀者可以想一想是如何變動的）。s[L ~ N-1]的打印與前面字符的打印沒有關(guān)系，可以看成一個新的目標(biāo)字符串，用同樣的方法分析計算。有兩個特殊情況：L=1時，s[0]==s[L-1]必然成立，這時的答案為1 + s[1 ~ N-1]的最小打印次數(shù)；L=N時，應(yīng)滿足s[0]==s[L-1]==s[N-1]，即左右兩端點(diǎn)相等，答案為s[1 ~ N-1]的最小打印次數(shù)。

Ⅴ. 分別計算出s[1 ~ L-1]、s[L ~ N-1]的最小打印次數(shù)并相加得到特定L下的打印次數(shù)，枚舉所有L，對得到的答案取最小值即可得到最終答案。這樣把一個區(qū)間分成兩個小的連續(xù)區(qū)間求解的方法屬于區(qū)間型動態(tài)規(guī)劃，狀態(tài)表示為f[i][j]表示從i到j(luò)這段子串最少打印次數(shù)。具體可以采用遞推的方式（應(yīng)先從小到大枚舉區(qū)間的長度，因?yàn)殚L區(qū)間的答案是由短區(qū)間的答案確定的）把所有可能的區(qū)間的答案都算出來，也可采用記憶化搜索的遞歸形式實(shí)現(xiàn)，邊界條件為：長度為1的區(qū)間的字符串最少打印次數(shù)為1。枚舉所有區(qū)間的時間復(fù)雜度為O(n^2)，枚舉分段點(diǎn)的時間復(fù)雜度為O(n)，故總的時間復(fù)雜度為O(n^3)，額外空間復(fù)雜度為O(n^2)。

參考程序

面試官角度分析

本題的最優(yōu)解法為區(qū)間型動態(tài)規(guī)劃，難度較大，特別是如何狀態(tài)轉(zhuǎn)移比較難想：以什么依據(jù)將區(qū)間分成兩段，分成兩段后如何求解，即使知道寫法，想要說出其中的原委、證明其正確性也不是易事。給出正確的解法可以strong hire。

題目答案鏈接

相關(guān)題目

專業(yè)的北美IT求職經(jīng)驗(yàn)分享，技術(shù)交流社區(qū)，幫助你找到好的IT工作。

由硅谷頂尖的IT企業(yè)工程師授課，提供專業(yè)的算法培訓(xùn)/面試咨詢。

官網(wǎng)：www.jiuz

微信公眾號：九章算法。

知乎ID：九章算法。