题目大意：
压缩字符串 II
行程长度编码 是一种常用的字符串压缩方法，它将连续的相同字符（重复 2 次或更多次）替换为字符和表示字符计数的数字（行程长度）。例如，用此方法压缩字符串 “aabccc” ，将 “aa” 替换为 “a2″ ，”ccc” 替换为` “c3” 。因此压缩后的字符串变为 “a2bc3” 。
注意，本问题中，压缩时没有在单个字符后附加计数 ‘1’ 。
给你一个字符串 s 和一个整数 k 。你需要从字符串 s 中删除最多 k 个字符，以使 s 的行程长度编码长度最小。
请你返回删除最多 k 个字符后，s 行程长度编码的最小长度 。
示例 1：
输入：s = "aaabcccd", k = 2 输出：4 解释：在不删除任何内容的情况下，压缩后的字符串是 "a3bc3d" ，长度为 6 。最优的方案是删除 'b' 和 'd'，这样一来，压缩后的字符串为 "a3c3" ，长度是 4 。
示例 2：
输入：s = "aabbaa", k = 2 输出：2 解释：如果删去两个 'b' 字符，那么压缩后的字符串是长度为 2 的 "a4"
示例 3：
输入：s = "aaaaaaaaaaa", k = 0 输出：3 解释：由于 k 等于 0 ，不能删去任何字符。压缩后的字符串是 "a11" ，长度为 3 。
提示：
1 <= s.length <= 1000 <= k <= s.lengths仅包含小写英文字母
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1531
解题思路分析：
这两周比较忙(懒)，都没赶上周赛，今天开始补作业。
将本题的描述换一种说法，实际上是让我们从字符串s中找到一个长度为length(s)-k的子序列，其行程长度编码的长度最短。我们可以将该子序列分成两部分，左半部分为1个或者多个连续相同字符c，右半部分为不以c开头任意子序列。分别求出左右两部分的编码长度，求和即是当前子序列编码后的长度。而右半部分我们又可以差分为两部分，他的左半部分为1个或者多个连续相同字符c'(c’!=c)，它的右半部分不以c’开头任意子序列。以此类推，这实际上是一个清晰的递归过程。我们举例来看，比如：
s = "abacad"; k=2;
因为k等于2，也就意味着我们需要在s中找到一个长度为4的子序列。我们从s下标为0处向后循环，当前字母为a，首先构建子序列的左半部分，即找到n个相同的a，对于本例，我们有三种选择方案：
- 选择第一个a，即子序列的左半部分为a，右半部分需要在bacad中找到一个长度为3的并不以a开头的序列（递归求解）。
- 选择前两个a，即子序列的左半部分为aa，右半部分需要在cad中找到一个长度为2的并不以a开头的序列（递归求解）。
- 选择前三个a，即子序列的左半部分为aaa，右半部分需要在d中找到一个长度为1的并不以a开头的序列（递归求解）。
除了上述三种情况，我们还可以向后查找以b开头或者以c开头的左半部分，所有选择中，编码后最短的子序列的长度即是返回结果。
总结来看，递归方法中我们需要使用到两层循环，第一层循环用来找到子序列左半部分的开头字母，第二层循环来控制该字母在子序列中连续出现的次数，也就是左半部分的长度。而右半部分交给递归子问题去处理。所有组合中，长度最短的即为当前递归的返回结果。
另外，递归方法一般都要有记忆数组相伴。递归函数的参数中，我们需要传递当前的index，即右半部分的起始位置，以及当前剩余长度count两个变量，因此使用一个二维记忆数组即可保存递归函数的转态（相当于动态规划解法中的DP数组）。这里，递归函数可以被描述为：从下标index开始向后，在所有长度为count的子序列中，找到编码后的最小长度并返回。
最后再看下可以优化的部分，第一层循环，我们在找左半部分的开头字母，因此循环中遇到已经出现过的字母时可以跳过。比如上例中的字符串abacad，我们从下标0向后循环，按照顺序先找以a开头的左半部分，接下来是以b开头，在接下来又是字母a，这里我们没有必要再做重复操作，从当前下标2开始做第二层循环与下标0处唯一的区别是，子序列左半部分的a的最大长度只能达到2，而这种情况已被下标0处的情况所包含。解题时，我们可以考虑使用一个访问数组来记录我们已经处理过的字母。
剩下的细节操作详见代码注释。
实现代码：
int[][] memo; // 记忆数组
public int getLengthOfOptimalCompression(String s, int k) {
memo=new int[s.length()][s.length()-k+1]; // 初始化记忆数组
return help(s.toCharArray(), 0, s.length()-k); // 递归求解
}
// 求从下标index开始向后，所有长度为count的子序列中，编码后的最小长度
int help(char[] arr, int index, int count){
if(count==0) return 0; // 子序列长度为0，返回0
if(index==arr.length){ // 当下标越界时还未找到长度为count的子序列
// 返回一个最大值，代表未找到合理解
return Integer.MAX_VALUE;
}
// 如果记忆数组中存在数值，直接返回
if(memo[index][count]>0) return memo[index][count];
int min=Integer.MAX_VALUE; // 当前最优解
boolean[] used = new boolean[26]; // 记录已经处理过的开头字母
// 从index向后循环，寻找左半部分的开头字母
for(int i=index;i<arr.length;i++){
if(used[arr[i]-'a']) continue; // 优化：已处理过当前的字母，跳过
// 优化：如果当前字母与上层递归的左半部分相同，跳过
if(index>0&&arr[i]==arr[index-1]) continue;
used[arr[i]-'a']=true; // 设当前字母已被处理过
int leftCount=0; // 左半部分长度
// 从当前下标开始向后循环，寻找相同字符（可不连续）
for(int j=i;j<arr.length;j++){
if(arr[j]!=arr[i]) continue; // 如果字符不相同，跳过
leftCount++; // 左半部分长度(相同字符个数)加一
if(count-leftCount<0) break; // 如果左半部分长度大于子序列长度，退出
int left=getLength(leftCount); // 计算左半部分编码后长度
int right=help(arr,j+1,count-leftCount); // 递归求解右半部分编码长度
if(right==Integer.MAX_VALUE) continue; // 若递归返回值为最大值，代表不和理解，跳过
int length=left+right; // 左右长度相加为当前子序列编码后长度
min=Math.min(min, length); // 更新最小值
}
}
memo[index][count]=min; // 将最小值存入记忆数组
return min;
}
// 计算左半部分编码后长度
// num：相同字符数量
int getLength(int num){
// 如果只有一个字母，返回长度1
if(num==1) return 1;
// 编码后长度，1代表字母占位长度
int length=1;
// 求num的位数
while(num>0){
length++;
num/=10;
}
return length;
} 本题解法执行时间为78ms。
Runtime: 78 ms, faster than 79.09% of Java online submissions for String Compression II.
Memory Usage: 39.9 MB, less than 100.00% of Java online submissions for String Compression II.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1531-string-compression-ii-解题思路分析/