471. Encode String with Shortest Length

字符串中相同的字符串压缩成『次数[字符串]』，且可以nested压缩，问压缩后最短长度。要求找最优的划分，action为在区间[i, j]内不断遍历可能的k使得分成左右两边，左右两边已本身是各自的最优划分结果，最后看哪个k使得两边拼接后长度最短。还有就是整个t = s[i, j]能被压缩，判断方法为让在t + t里看t第二次出现的位置是否小于t的长度，小于说明能以t内元素做平移，也就是t本身是某字符串重复组成。如果按照正常i,j遍历，在递推时dp[i, j]时不知道dp[k + 1, j]的值，因此换个思路，用字符串长度为基本遍历条件。

答案参考自这。

class Solution {
public:
    string encode(string s) {
        const int N = s.length();
        vector<vector<string>> dp(N, vector<string>(N));
        for (int len = 1; len <= N; ++len) {
            for (int i = 0; i + len - 1 < N; ++i) {
                int j = i + len - 1;
                dp[i][j] = s.substr(i, j);
                for (int k = i; k < j; ++k) {
                    string &l = dp[i][k], &r = dp[k + 1][j];
                    if (left.size() + r.size() < dp[i][j].size()) {
                        dp[i][j] = l + r;
                    }
                }
                string replace = "";
                string t = s.substr(i, j - i + 1);
                auto pos = (t + t).find(t, 1);
                if (pos >= t.size()) {
                    replace = t;
                } else {
                    replace = to_string(t.size() / pos) + '[' + dp[i][i + pos - 1] + ']'
                }
                if (replace.length() < dp[i][j].size()) dp[i][j] = replace;
            }
        }
    }
};