[LeetCode]Encode String with Shortest Length

区间DP的问题，我们用dp[i][j]表示子串s[i:j]的最小压缩串，我们有如下递推方程：

• dp[i][j] = min(dp[i][k] + dp[k + 1][j]), where 1 <= k < j, '+' means concatenate here
• dp[i][j] = min(dp[i][j], compress(s[i:j])), compress is a function to find if we can shorten input string by find a repeating pattern in itself

这里compress的功能是，找到string自身的重复串来压缩string。比如对于abcabcabc，我们只进行区间dp是没有办法找到3[abc]的，所以我们必须对自身进行compress。对自身进行压缩的就是寻找自身最小覆盖子串的过程。有多个覆盖子串我们肯定是取最小的，对于d[str]的形式，如果我们double str的长度最多也就使得d减少一位，所以str越短越好。

时间复杂度O(n^3)，寻找自身最小覆盖子串需要线性时间，代码如下：