471.最短の長さで文字列をエンコードする

471 Encode String With Shortest Length

http://www.cnblogs.com/grandyang/p/6194403.html

解決策：DP

考え：
2次元DP配列を作成します。ここで、dp [i] [j]は、範囲[i、j]内の文字列sの省略形を表します（省略形が部分文字Stringより長い場合は、部分文字列を保持します） ）、s文字列の長さがnの場合、必要な最終結果はdp [0] [n-1]に格納され、sのすべての部分文字列をトラバースする必要があります。任意の部分文字列[i、j] 、中央に任意の位置kを持つ2つのセグメントに分割し、dp [i] [k]とdp [k + 1] [j]の全長およびdp [i] [j]の長さを比較し、割り当てます。小さい文字列をdp [i] [j]にすると、sの範囲[i、j]の部分文字列tをマージするだけです。マージする方法は、抽出された文字列tの後にtを追加してから、部分文字列tの2番目の開始位置を探すことです。 2番目の開始位置がtの長さよりも短い場合、tには繰り返し文字列が含まれます。たとえば、t = 'abab'、次にt + t = 'abababab'の場合、2番目のtが2に現れる位置を見つけます。 t 4の長さよりも、tが存在することを示します。繰り返し、繰り返しの数はt.size（）/ pos = 2です。次に、繰り返しの場所を角かっこで囲む必要があります。部分文字列を直接に配置することはできないことに注意してください。括弧ですが、dpからのものである必要があります。タイトルの例5のように、繰り返される部分が省略形として記述されている可能性があるため、対応する位置の文字列が取り出されます。 t = 'abc'の場合、t + t = 'abcabc'の場合、2番目のtが3に現れる位置を見つけます。これは、tの長さ3に等しく、tに繰り返しがないことを示し、置き換えます。まだtです。次に、replaceとdp [i] [j]で取得した文字列の長さを比較し、小さい方の長さをdp [i] [j]に割り当てます。時間計算量は、O（n）です。^{3）、スペースの複雑さはO（n}二）
時間計算量：O（N ^ 3）空間計算量：O（N ^ 2）

ソリューションコード：

class Solution { public String encode(String s) { String[][] dp = new String[s.length()][s.length()] for(int l=0l