主題
題目連結：
題目意譯：
連續長度編碼（Run-Length Encoding）是一個字串壓縮方法，其運作方式為將連續的相同字元（重複 2 或多次）替換成該字元與連續出現次數（長度）連接後所形成的字串。例如說，為了將字串 "aabccc" 壓縮，我們將 "aa" 替換成 "a2"、"ccc" 替換成 "c3"。因此壓縮後的字串為 "a2bc3"。
注意到在此問題中，我們不會在單一字元後面加上 '1'。
給定一字串 s 以及一整數 k。你需要從 s 中刪除最多 k 個字元使得經過連續長度編碼後的 s 之長度最小化。
找到藉由從 s 中刪除最多 k 個字元後可以得到的 s 之連續長度編碼的最小長度。
限制：
1 ≦ s.length ≦ 100
0 ≦ k ≦ s.length
s 只包含小寫英文字母。
範例測資：
範例 1：
輸入： s = "aaabcccd", k = 2
輸出： 4
解釋：
在不刪除任何東西的情況下壓縮 s 將得到 "a3bc3d"，其長度為 6。刪除若干個 'a' 或 'c' ，將最多將壓縮後的長度減少至 5。例如說刪除 2 個 'a' 將得到 s = "abcccd"，其將會被壓縮成 "abc3d"。因此最佳的策略為刪除 'b' 和 'd'，則壓縮後的 s 字串將變為 "a3c3"，其長度為 4。
範例 2：
輸入： s = "aabbaa", k = 2
輸出： 2
解釋： 如果我們將兩個字元 'b' 都刪除掉，則壓縮的結果字串將會是 "a4"，其長度為 2。
範例 3：
輸入： s = "aaaaaaaaaaa", k = 0
輸出： 3
解釋： 由於 k 是 0，我們無法刪除任何東西。壓縮後的字串為 "a11"，其長度為 3。
解題思維：
可以看到為了把編碼的長度縮短，我們能做的就是盡可能把兩群相同的字元藉由刪除它們之間的字元來連接在一起，這樣一來「可能可以」使得編碼的長度縮短。但問題是我們並不能馬上知道合併哪些相同字元之群體是最佳策略。
而這時動態規劃（Dynamic Programming，DP）的精神便可以派上用場——不知道要做哪些「子問題」？那就全做吧！
定義一個二維陣列 D，其中 D[i][j] 代表在 s 前 i 個字元已經被考慮過（有些可能已經被刪除）且剩下 j 次刪除字元的機會的狀況下，剩餘字元的連續長度編碼最短可以多短。可以看到 D[0][k] 即為原題目之條件。
並且可觀察出其遞迴式為：
（以下的 i 值皆滿足 0 ≦ i <= s.length）
D[i][x] = 0，其中 0 ≦ x ≦ k 且 s.length - i ≦ x（代表剩下的字元可以直接刪光光，此為遞迴停止條件）、
反之，D[i][x] = min(D[i + 1][x - 1], D[j + 1][y])，其中 i ≦ j < s.length 且 s[i] ～ s[j] 這個子字串中有 x - y 個字元與 s[i] 不同（這些不同的字元是要被刪除的）。min() 中前面那一項代表著刪除 s[i] 的選項，後面則代表著留下 s[i]「試圖」與後面的字元合併的那些選項。
因為不像一般 DP 之題型有著明顯的順序可以根據遞迴式條件依序填入每一格格子的答案（其實還是有，但比較複雜一點），因此直接遞迴求解並在過程中記錄已經求過的子問題即可（類似這題）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
