一、最长递增子序列（LIS）
给定数组arr，返回arr的最长递增子序列。例如，arr={2,1,5,3,6,4,8,9,7}，返回的最长递增子序列为{1,3,4,5,8,9}
1.时间复杂度为O(N2)的方法
第一步：生成长度为N的数组dp，dp[i]表示在以arr[i]这个数结尾的情况下，arr[0...i]中的最大递增子序列长度，其中arr[0]=1
第二步：要计算dp[i]，如果最长递增子序列以arr[i]结尾，那么在arr[0...i]中所有比arr[i]小的数都可以作为倒数第二个数。在这么多倒数第二个数中，以哪个数结尾的最大递增子序列最大，就选那个数作为倒数第二个数，即dp[i] = max{dp[j] + 1(0 <= j < i，arr[j]<arr[i])}。如果arr[0...i]中所有的数都不比arr[i]小，令dp[i]=1即可。可以求出的dp={1,1,2,2,3,3,4,5,4}
public int[] getdp1(int[] arr) { int[] dp = new int[arr.length]; for (int i = 0; i < dp.length; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + 1); } } return dp; }
第三步：目前已经求得的dp数组为dp={1,1,2,2,3,3,4,5,4}，下面分为4步找到最长递增子序列
（1）遍历dp数组，找到最大值以及位置。最大值的位置就是最长子序列的结尾。例如，最大值为5，位置为7，则arr[7]=9是结尾。
（2）从arr数组的位置7开始从右向左遍历，如果对于某一个arr[i]<arr[7]并且dp[i] = dp[7] - 1，那么说明arr[i]可以作为arr[7]的前面一个数，例如arr[6] < arr[7]并且dp[6] = dp[7] - 1，因此arr[6] = 8应该作为倒数第二个数，目前确定了8 9
（3）对于有重复的数字，例如arr[5]和arr[4]都满足小于8，并且dp[5]和dp[4]的值都是3，因此选择这两个数中其中一个都可以
（4）重复上述过程，直到遍历完所有的数即可。
public int[] generateLIS(int[] arr, int[] dp) { int len = 0, index = 0; for (int i = 0; i < dp.length; i++) { if (dp[i] > len) { len = dp[i]; // 找到最长的长度 index = i; // 找到结尾的数的位置 } } int[] lis = new int[len]; lis[--len] = arr[index]; for (int i = index; i >= 0; i--) { if (arr[i] < arr[index] && dp[i] == dp[index] - 1) { lis[--len] = arr[i]; index = i; } } return lis; }
第四步：写出总的方法
public int[] lis1(int[] arr) { if (arr == null || arr.length == 0) return null; int[] dp = getdp1(arr); return generateLIS(arr, dp); }
计算dp数组过程的时间复杂度为O(N2)，而根据dp数组得到最长递增子序列的时间复杂度为O(N)，因此整个过程的时间复杂度为O(N2)。如果想让时间复杂度达到O(NlogN)，那么只需要让计算dp数组的过程达到O(NlogN)即可，而根据dp计算出最长递增子序列的过程是一样的。
2.时间复杂度为O(NlogN)的二分查找算法
生成一个长度为N的数组ends，初始时ends[0]=arr[0]，其他位置上为0。生成整型变量righ，初始时right=0。从左到右遍历时，ends[0...right]为有效区，ends[right+1...N-1]为无效区。ends[3]=7的意思就是，在所有长度为4的递增序列中，最小的结尾数就是7。如果来的数大于7，那么长度一定可以达到5，如果来的树大于4小于7，那么长度还是4。
arr = [2,1,5,3,6,4,8,9,7],
0.arr[0]=2,dp=[1],ends=[2]
1.arr[1]=1,dp=[1,1],ends=[1],1<2,2对应的dp为1，因此也是1，
2.arr[2]=5,dp=[1,1,2],ends=[1,5],没有发现比5大的数，dp为原dp+1为2
3.arr[3]=3,dp=[1,1,2,2],ends=[1,3]，发现3比5小，5对应的dp是2，因此也是2
4.arr[4]=6,dp=[1,1,2,2,3],ends=[1,3,6]，没有发现比6大的数，dp为原dp+1为3
5.arr[5]=4,dp=[1,1,2,2,3,3],ends=[1,3,4]，发现4比6小，6对应的dp是3，因此也是3
6.arr[6]=8,dp=[1,1,2,2,3,3,4],ends=[1,3,4,8]，没有发现比8大的数，dp为原dp+1为4
7.arr[7]=9,dp=[1,1,2,2,3,3,4,5],ends=[1,3,4,8,9]，没有发现比9大的数，dp为原dp+1为5,
8.arr[8]=7,dp=[1,1,2,2,3,3,4,5,4],ends=[1,3,4,7,9]，发现7比8小，8对应的dp是4，因此也为4
利用这种方法得到的代码：例如在第5步时arr[5]=6，此时ends=[1,3,6]，则right=2，然后经过二分查找，l=2，right=2，ends[2]=4，dp[5]=2+1=3
public int[] getdp2(int[] arr) { int[] dp = new int[arr.length]; int[] ends = new int[arr.length]; ends[0] = arr[0]; dp[0] = 1; int right = 0; int l = 0, r = 0, m = 0; for (int i = 1; i < arr.length; i++) { l = 0; r = right; while (l <= r) { m = (l + r) / 2; if (arr[i] > ends[m]) { l = m + 1; } else { r = m - 1; } } right = Math.max(right, l); ends[l] = arr[i]; dp[i] = l + 1; } return dp; }
二、最长公共子序列（LCSE）
问题：给定两个字符串str1和str2，返回两个字符串的最长公共子序列。
例如str1=“1A2C3D4B56”，str2=“B1D23CA45B6A”，其中“123456”和“12C4B6”都是最长公共子序列，返回哪一个都行。
如果str1的长度为M，str2的长度为N，生成大小为M×N的矩阵dp，dp[i][j]的含义是str1[0...i]与str2[0...j]的最长公共子序列的长度。
第一步：矩阵dp的第一列，即dp[0...M-1][0]的含义是str1[0...i]与str2[0]的最长公共子序列长度，如果str1[i]==str2[0]，令dp[i][0]=1，且dp[i+1...M-1][0]也都为1，例如，如果str1[0...M-1]=“ABCDE”，并且str2[0]=“B”，那么str1[0]为“A”，不和“B”相等，因此dp[0][0]=0，而str1[1]=B，所以dp[1][0]=1，那么ABC、ABCD、ABCDE和str2的最长公共子序列长度一定为1，所以dp[2...4][0]都等于1
第二步：矩阵dp的第一行，和第一列同理，如果str1[0] == str2[j]，那么dp[0][j]=1，并且dp[0][j+1...N-1]=1
第三步：对于其他的位置(i,j)来说，只可能存在下面的三种情况（也可以分为两种情况str1[i] == str2[j]和str1[i] != str2[j]），在这三种情况中选择较大的dp[i][j]值即可。
- dp[i-1][j]：也就是str1[0...i-1]和str2[0...j]的最长公共子序列长度。例如，str1=“A1BC2”，str2=“AB34C”，dp[3][4]=3，因为“A1BC”和“AB34C”的最长公共子序列为“ABC”，而“A1BC2”和“AB34C”的公共子序列也是“ABC”，因此dp[4][4]也等于3
- dp[i][j-1]，例如，str1=“A1B2C”，str2=“AB3C4”，dp[4][3]=3，但是dp[4][4]也等于3
- 如果str1[i] == str2[j]，还可能是，比如：str1=“ABCD”，str2=“ABCD”，dp[2][2]=3，由于str1[3] == str2[3]，于是dp[3][3]=4
简化成一个模型来分析：A对应dp[i-1][j-1]，B对应dp[i-1][j]，C对应dp[i][j-1]，如果要求D也就是dp[i][j]的值：
如果str1[i]不等于str2[j]，那么只需比较B和C即可，选择其中较大的；如果str1[i]等于str2[j]，此时还需要比较A+1、B和C
A B
C D
获得dp的代码为：
public int[][] getdp(char[] str1, char[] str2){ int[][] dp = new int[str1.length][str2.length]; dp[0][0] = str1[0] == str2[0] ? 1 : 0; for (int i = 1; i < str1.length; i++) dp[i][0] = Math.max(dp[i-1][0], str1[i] == str2[0] ? 1 : 0); for (int j = 1; j < str2.length; j++) dp[0][j] = Math.max(dp[0][j-1], str1[0] == str2[j] ? 1 : 0); for (int i = 1; i < str1.length; i++) { for (int j = 1; j < str2.length; j++) { dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); if (str1[i] == str2[j]) dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + 1); } } return dp; }
得到的dp矩阵为：
B 1 D 2 3 C A 4 5 B 6 A
1 0 1 1 1 1 1 1 1 1 1 1 1 A 0 1 1 1 1 1 2 2 2 2 2 2 2 0 1 1 2 2 2 2 2 2 2 2 2 C 0 1 1 2 2 3 3 3 3 3 3 3 3 0 1 1 2 3 3 3 3 3 3 3 3 D 0 1 2 2 3 3 3 3 3 3 3 3 4 0 1 2 2 3 3 3 4 4 4 4 4 B 1 1 2 2 3 3 3 4 4 5 5 5 5 1 1 2 2 3 3 3 4 5 5 5 5 6 1 1 2 2 3 3 3 4 5 5 6 6
第4步：dp矩阵的右下角的值就代表str1和str2的最长公共子序列长度。如何根据dp矩阵求得最长公共子序列
（1）从矩阵的右下角开始，有三种移动方式：上，左和左上，假设在移动的过程中，i表示此时的行数，j表示此时的列数，同时用一个变量res表示最长公共子序列。
（2）如果dp[i][j]大于dp[i-1][j]和dp[i][j-1]，说明在之前计算dp[i][j]的时候，一定是选择了dp[i-1][j-1]+1，可以确定的是str[i]等于str[j]，并且这个字符一定是属于最长公共子序列，把这个字符放进res，然后向左上方移动。
（3）如果dp[i][j]等于dp[i-1][j]，说明在之前计算dp[i][j]的时候，dp[i-1][j-1]+1不是必须选择的，此时向上方移动即可，同理，如果dp[i][j]等于dp[i][j-1]，此时向左方移动即可，如果dp[i][j]同时等于dp[i-1][j]和dp[i][j-1]，那么此时向上还是向左移动都可以。总体来说，就是求dp矩阵的逆过程。（上图dp矩阵中黑体的部分就是）
public String lcse(String str1, String str2) { if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) return ""; char[] chs1 = str1.toCharArray(); char[] chs2 = str2.toCharArray(); int[][] dp = getdp(chs1, chs2); int m = chs1.length - 1; int n = chs2.length - 1; char[] res = new char[dp[m][n]]; int index = res.length - 1; while (index >= 0) { if (n > 0 && dp[m][n] == dp[m][n-1]) { n--; } else if (m > 0 && dp[m][n] == dp[m-1][n]) { m--; } else { res[index--] = chs1[m]; m--; n--; } } return String.valueOf(res); }
总结：计算dp矩阵时，时间复杂度为O(M×N)，空间复杂度为O(M×N)，通过dp矩阵得到最长公共子序列的时间复杂度为O(M+N)，空间复杂度为O(M×N)，因此，总的时间复杂度为O(M×N)，空间复杂度为O(M×N)
三、最长公共子串（LCST）
题目：给定两个字符串str1和str2，返回两个字符串的最长公共子串。
举例：str1=“1AB2345CD”，str2=“12345EF”，返回“2345”
要求：如果str1的长度为M，str2的长度为N，时间复杂度为O(M×N)，空间复杂度为O(1)
1.空间复杂度为O(M×N)的算法
首先生成一个大小为M×N的矩阵dp。dp[i][j]的含义是，在必须把str1[i]和str2[j]当作公共子串最后一个字符的情况下，公共子串最长能有多长。例如：str1=“A1234B”，str2=“CD1234”，dp[3][4]表示在必须把str1[3]也就是‘3’和str2[4]也就是‘3’当作公共子串最后一个子串的情况下，公共子串最长能有多长，由于最长公共子串为“123”，因此dp[3][4]=3。如果不能构成公共子串，则令其为0。
第一步：矩阵第一列，即dp[0...M-1][0]。对于某个位置(i,0)来说，如果str1[i]==str2[0]，则令dp[i][0]=1，否则为0。
第二步：矩阵第一行，即dp[0][0...M-1]。对于某个位置(0,j)来说，如果str1[0]==str2[j]，则令dp[0][j]=1，否则为0。
第三步：其他位置从左往右，从上往下计算。dp[i][j]的值只能有两种情况：
- 如果str1[i] != str2[j]，则说明必须把str1[i]和str2[j]当作公共子串最后一个字符是不可能的，令dp[i][j]=0
- 如果str1[i] == str2[j]，则说明可以把str1[i]和str2[j]当作公共子串的最后一个字符，那么此时最长公共子串的长度是什么呢？如果dp[i-1][j-1]的长度不等于0，则说明前一对已经相等了，于是长度为dp[i-1][j-1]+1，如果前一对不相等，即dp[i-1][j-1]=0，那么现最长长度为1，也就是dp[i-1][j-1]+1。总的来说，dp[i][j] = dp[i-1][j-1]+1
str1=“A1234B”，str2=“CD1234”得到的dp矩阵为：
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 3 0 0 0 0 0 0 4 0 0 0 0 0 0
此时的计算dp的代码为：
public int[][] getdp(char[] str1, char[] str2){ int[][] dp = new int[str1.length][str2.length]; for (int i = 0; i < str1.length; i++) { if (str1[i] == str2[0]) dp[i][0] = 1; } for (int j = 0; j < str2.length; j++) { if (str2[j] == str1[0]) dp[0][j] = 1; } for (int i = 1; i < str1.length; i++) { for (int j = 1; j < str2.length; j++) { if (str1[i] == str2[j]) { dp[i][j] = dp[i-1][j-1] + 1; } } } return dp; }
第四步：根据dp找到最长公共子串，也就是依次找到最大值及其位置（例如上图dp矩阵中的1-2-3-4）即可。
public String lcst(String str1, String str2) { if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) return ""; char[] chs1 = str1.toCharArray(); char[] chs2 = str2.toCharArray(); int[][] dp = getdp(chs1, chs2); int end = 0; int max = 0; for (int i = 0; i < chs1.length; i++) { for (int j = 0; j < chs2.length; j++) { if (dp[i][j] > max) { end = i; max = dp[i][j]; } } } return str1.substring(end - max + 1, end + 1); }
2.空间复杂度为O(1)的算法
在之前的dp矩阵中，可以看到有非常多的0，然而这些位置上的0其实都是可以不要的，实际在计算每一个dp[i][j]的时候，最多只需要其左上方dp[i-1][j-1]的值，也就是每一条斜线。每一条斜线在计算之前生成整型变量len，len表示左上方的值，初始时len=0，假设计算到(i,j)，此时len表示(i-1,j-1)的值，如果str1[i]=str2[j]，那么位置(i,j)的值为len+1，如果不相等，则len=0。用变量max记录所有的len中的最大值，然后用end记录其位置即可
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 2 0 0 0 0 3 0 0 0 0 0 3 0 0 0 0 0 4 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 ...
此时，空间复杂度为O(1)的代码为：
public String lcst1(String str1, String str2) { if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) return ""; char[] chs1 = str1.toCharArray(); char[] chs2 = str2.toCharArray(); int row = 0; // 斜线开始位置的行 int col = chs2.length - 1; // 斜线开始位置的列 int max = 0; // 记录最大长度 int end = 0; // 最大长度更新时，记录子串的结尾位置 while (row < chs1.length) { int i = row; int j = col; int len = 0; // 从(i,j)开始向右下方遍历 while (i < chs1.length && j < chs2.length) { if (chs1[i] != chs2[j]) { len = 0; } else { len++; } // 记录最大位置，以及结束字符的位置 if (len > max) { end = i; max = len; } i++; j++; } if (col > 0) { // 斜线开始的位置的列先向左移动 col--; } else { // 列移动到最左之后，行向下移动 row++; } } return str1.substring(end - max + 1, end + 1); }
四、最长连续序列
问题：给定无序数组arr，返回其中最长的连续序列的长度
举例：arr=[100,4,200,1,3,2]，最长的连续序列为[1,2,3,4]，所以返回4
解答：可以利用哈希表实现时间复杂度为O(N)，空间复杂度为O(N)的方法：
第一步：生成哈希表，其中key代表遍历过的某个数，value代表key这个数所在的最长连续序列的长度。
第二步：从左到右遍历arr，假如遍历到arr[i]，如果arr[i]之前出现过，直接遍历下一个数。如果没有出现过，首先在map中加入(arr[i],1)，代表目前arr[i]单独作为一个连续序列。然后看map中是否含有arr[i]-1，如果有，则说明arr[i]-1所在的序列可以和arr[i]合并，合并后记为A序列。利用map可以得到A序列的长度，即为lenA，最小值记为leftA，最大值记为rightA，只在map中更新与leftA和rightA有关的记录，更新成(left,lenA)和(right,rightA)，然后看map中是否有arr[i]+1，如果有和A同理的操作。
public int merge(Map<Integer, Integer> map, int less, int more) { int left = less - map.get(less) + 1; int right = more + map.get(more) - 1; int len = right - left + 1; map.put(left, len); map.put(right, len); return len; }
第三步：遍历的过程中用全局变量max记录每次合并出的序列的长度最大值，最后返回max。
public int longestConsecutive(int[] arr) { if (arr == null || arr.length == 0) return 0; int max = 1; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < arr.length; i++) { if (!map.containsKey(arr[i])) map.put(arr[i], 1); if (map.containsKey(arr[i] - 1)) max = Math.max(max, merge(map, arr[i] - 1, arr[i])); if (map.containsKey(arr[i] + 1)) max = Math.max(max, merge(map, arr[i], arr[i]+1)); } return max; }
整个过程中，只是每个连续序列最小值和最大值在map中的记录有意义，中间的记录不再更新，因为再也不会使用到。这是因为我们只处理之前没出现过的数，如果一个没出现的数能够把某个连续区间扩大，或把两个连续区间连在一起，就只需要更新连续区间最小值和最大值就可以了。
以arr=[100,4,200,1,3,2]为例，初始时max=1 100进map，此时map中{100=1} 4进map，此时map中{100=1, 4=1} 200进map，此时map中{100=1, 4=1, 200=1} 1进map，此时map中{1=1, 100=1, 4=1, 200=1} 3进map，此时因为map中有4，于是合并3和4，更新max=2，此时map中{1=1, 3=2, 100=1, 4=2, 200=1}
2进map，首先合并1和2，1=2，2=2，max更新为3，然后合并2和3，1=4,4=4（不关心2和3），max更新为4，最后map有{1=4, 2=2, 3=2, 100=1, 4=4, 200=1
代码为：主要理解merge方法中的只顾连续序列的首尾而不管首尾中间的值的技巧。
public int longestConsecutive(int[] arr) { if (arr == null || arr.length == 0) return 0; int max = 1; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < arr.length; i++) { if (!map.containsKey(arr[i])) map.put(arr[i], 1); if (map.containsKey(arr[i] - 1)) max = Math.max(max, merge(map, arr[i] - 1, arr[i])); if (map.containsKey(arr[i] + 1)) max = Math.max(max, merge(map, arr[i], arr[i]+1)); } return max; }
五、最小编辑代价（Minimum edit cost）
问题：给定两个字符串str1和str2，在给定三个整数ic、dc和rc，分别代表插入、删除和替换一个字符的代价，返回将str1编辑成str2的代价。
举例：str1=“abc”，str2=“adc”，ic=5，dc=3，rc=2，那么把“b”替换成“d”的代价是最小的，为2.
str1=“abc”，str2=“adc”，ic=5，dc=3，rc=100，那么先删除b，然后插入d的代价是最小的，为8
1.空间复杂度为O(M×N)的算法
动态规划表dp：大小为(M+1)×(N+1)，因为字符串中“”也是其子串，dp[i][j]表示str1[0...i-1]编辑成str2[0...j-1]的最小代价。
第一步：dp[0][0]表示str1空的子串编辑成str2空的子串的代价为0
第二步：dp矩阵的第一列，即dp[0...M-1][0]。dp[i][0]表示str1[0...i-1]编辑成空子串的最小代价，显然是把str1[0...i-1]全部删掉，因此dp[i][0]=dc*i
第三步：dp矩阵的第一行，即dp[0][0...N-1]。dp[0][j]表示空串编辑成str2[0...j-1]的最小代价，显然是把str2[0...j-1]全部插入，因此dp[0][j]=ic*i
第四步：其他位置按照从左到右，从上到下计算，dp[i][j]的值只能来自下面的四种情况
- str1[0...i-1]可以先编辑成str1[0...i-2]，也就是删除字符str1[i-1]，然后由str1[0...i-2]编辑成str2[0...j-1]，而dp[i-1][j]表示str1[0...i-2]编辑成str2[0...j-1]的最小代价，那么此时dp[i][j]=dc+dp[i-1][j]
- str1[0...i-1]可以先编辑成str2[0...j-2]，这一过程可以用dp[i][j-1]表示，然后再由str2[0...j-2]插入一个str2[j-1]变成str2[0...j-1]，那么此时dp[i][j]=ic+dp[i][j-1]
- 如果str1[i-1] != str2[j-1]，也就是str1的最后一位和str2的最后一位不相等，那么可以先把str1[0...i-2]部分变成str2[0...j-2]，可以用dp[i-1][j-1]表示，然后把str1的最后一位替换成str2的最后一位即可，此时dp[i][j] = dp[i-1][j-1] + rc
- 如果str1[i-1] == str2[j-1]，也就是str1的最后一位已经和str2的最后一位相等，那么根据上面的分析，此时dp[i][j]就直接是dp[i-1][j-1]
第五步：在上面的四种情况中，选择最小的值作为dp[i][j]，然后dp右下角的值就是最终的结果。
假设：str1 = "ab12cd3"，str2 = "abcdf"，ic = 5, dc = 3, rc = 2;则dp矩阵为
"" a b c d f
"" 0 5 10 15 20 25
a 3 0 5 10 15 20
b 6 3 0 5 10 15
1 9 6 3 2 7 12
2 12 9 6 5 4 9
c 15 12 9 6 7 6
d 18 15 12 9 6 9
3 21 18 15 12 9 8
空间复杂度为O(M×N)的代码为：
public int minCost1(String str1, String str2, int ic, int dc, int rc) { if (str1 == null || str2 == null) return 0; char[] chs1 = str1.toCharArray(); char[] chs2 = str2.toCharArray(); int row = chs1.length + 1; int col = chs2.length + 1; int[][] dp = new int[row][col]; for (int i = 1; i < row; i++) dp[i][0] = dc * i; for (int j = 1; j < col; j++) dp[0][j] = ic * j; for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { if (chs1[i-1] == chs2[j-1]) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = dp[i-1][j-1] + rc; } dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + ic); dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + dc); } } return dp[row-1][col-1]; }
2.空间复杂度为O(min{M,N})的算法
在使用空间压缩的方法时，和之前“矩阵的最小路径和”的使用dp数组不同的是，之前的dp[i][j]仅依赖两个位置的值dp[i-1][j]和dp[i][j-1]，滚动数组时求dp[j]的时候，dp[j]没有更新之前相等于dp[i-1][j]的值，而dp[j-1]的值又已经更新过相当于dp[i][j-1]的值。而这里的dp[i][j]还依赖dp[i-1][j-1]，因此还需要一个变量来保存dp[j-1]没更新之前的值，也就是dp[i-1][j-1]。另外，对于dp数组长度问题，还是使用str1和str2中较短的一个作为列对应的字符串，长度较长的作为行对应的字符串，如果此时str1做了列对应的字符串，那么也就是由str2如何变到str1，str1变成str2的插入过程，就对应着str2变成str1的删除过程，于是此时把插入代价和删除代价交换就可以了。
public int minCost2(String str1, String str2, int ic, int dc, int rc) { if (str1 == null || str2 == null) return 0; char[] chs1 = str1.toCharArray(); char[] chs2 = str2.toCharArray(); char[] longstr = chs1.length >= chs2.length ? chs1 : chs2; char[] shortstr = chs1.length < chs2.length ? chs1 : chs2; if (chs1.length < chs2.length) { // 如果str2较长，那么就交换ic到dc int tmp = ic; ic = dc; dc = tmp; } int[] dp = new int[shortstr.length + 1]; for (int i = 1; i < shortstr.length; i++) dp[i] = ic*i; for (int i = 1; i <= longstr.length; i++) { int pre = dp[0]; // pre保存左上角的值 dp[0] = dc * i; for (int j = 1; j <= shortstr.length; j++) { int tmp = dp[j]; // 将没更新之前的dp[j]先保存下来 if (longstr[i-1] == shortstr[j-1]) { dp[j] = pre; } else { dp[j] = pre + rc; } dp[j] = Math.min(dp[j], dp[j-1] + ic); dp[j] = Math.min(dp[j], tmp + dc); pre = tmp; // pre变成下一轮dp[j]没更新前的值 } } return dp[shortstr.length]; }
六、交错字符串（Staggered String）
问题：给定三个字符串str1、str2和aim，如果aim包含且仅包含来自str1和str2的所有字符，并且aim中属于str1和str2的字符都和在原字符串中顺序一致，那么aim是str1和str2的交错字符串。判断aim是否是由str1和str2交错形成。
举例：str1=“AB”，str2=“12”，那么“AB12”、“A1B2”、“A12B”、“1A2B”和“1AB2”等都是str1和str2的交错字符串。
1.空间复杂度为O(M×N)的算法
动态规划矩阵dp：大小为(M+1)×(N+1)，dp[i][j]表示aim[0...i+j-1]能否被str1[0...i-1]和str[j-1]交错组成。dp[M][N]表示aim整体能够被str1整体和str2整体交错组成。
第一步：dp[0][0] = true，也就是aim为空串时，当然可以被str1为空串和str2为空串交错组成
第二步：dp矩阵的第一列，即dp[0...M-1][0]，dp[i][0]表示aim[0...i-1]能够只被str1[0...i-1]交错组成，那也就是如果aim[0...i-1]等于str1[0...i-1]，则dp[i][0]=true，否则返回false
第三步：dp矩阵的第一行，即dp[0][0...N-1]，dp[0][j]表示aim[0...j-1]能够只被str2[0...j-1]交错组成，那也就是如果aim[0...j-1]等于str2[0...j-1]，则dp[0][j]=true，否则返回false
第四步：对于其他位置(i,j)，dp[i][j]的值由下面的几种情况决定：
- dp[i-1][j]代表aim[0...i+j-2]能够被str1[0...i-2]和str2[0..j-1]交错形成，如果可以，那么如果再有str1[i-1]等于aim[i+j-1]，说明str1[i-1]又可以作为交错形成aim[0...i+j-1]的最后一个字符，令dp[i][j]=true
- dp[i][j-1]代表aim[0...i+j-2]能够被str1[0...i-1]和str2[0...j-2]交错形成，如果可以，那么如果再有str2[j-1]等于aim[i+j-1]，说明str2[j-1]又可以作为交错形成aim[0...i+j-1]的最后一个字符，令dp[i][j]=true
- 如果上面两种情况都不满足，则令dp[i][j]=false
假设：str1 = "AB", str2 = "12", aim = "1A2B"
'' '1' '2'
'' true true false
'A' false true true
'B' false false true
空间复杂度为O(M×N)的代码为：
public boolean isCross1(String str1, String str2, String aim) { if (str1 == null || str2 == null || aim == null) return false; char[] chs1 = str1.toCharArray(); char[] chs2 = str2.toCharArray(); char[] chaim = aim.toCharArray(); if (chaim.length != chs1.length + chs2.length) return false; boolean[][] dp = new boolean[chs1.length + 1][chs2.length + 1]; dp[0][0] = true; for (int i = 1; i <= chs1.length; i++) { if (chs1[i - 1] != chaim[i - 1]) break; dp[i][0] = true; } for (int j = 1; j <= chs2.length; j++) { if (chs2[j - 1] != chaim[j - 1]) break; dp[0][j] = true; } for (int i = 1; i <= chs1.length; i++) { for (int j = 1; j <= chs2.length; j++) { if ((chs1[i-1] == chaim[i+j-1] && dp[i-1][j]) || (chs2[j-1] == chaim[i+j-1] && dp[i][j-1])){ dp[i][j] = true; } } } return dp[chs1.length][chs2.length]; }
2.空间复杂度为O(min{M,N})的算法
由于dp[i][j]只与dp[i-1][j]和dp[i][j-1]有关，因此和常规的空间压缩方法一样，比较str1和str2的长度，选择长度较小的那个作为列对应的字符串，然后生成和较短字符串长度一样的一维数组dp，滚动更新（即从左往右，从上往下）即可
public boolean isCross2(String str1, String str2, String aim) { if (str1 == null || str2 == null || aim == null) return false; char[] chs1 = str1.toCharArray(); char[] chs2 = str2.toCharArray(); char[] chaim = aim.toCharArray(); if (chaim.length != chs1.length + chs2.length) return false; char[] longstr = chs1.length >= chs2.length ? chs1 : chs2; char[] shortstr = chs1.length < chs2.length ? chs1 : chs2; boolean[] dp = new boolean[shortstr.length + 1]; dp[0] = true; for (int i = 1; i <= chs1.length; i++) { if (shortstr[i - 1] != chaim[i - 1]) break; dp[i] = true; } for (int i = 1; i <= longstr.length; i++) { dp[0] = dp[0] && longstr[i - 1] == chaim[i - 1]; for (int j = 1; j <= shortstr.length; j++) { if ((longstr[i-1] == chaim[i+j-1] && dp[i]) || shortstr[j-1] == chaim[i+j-1] && dp[j-1]) { dp[j] = true; } else { dp[j] = false; } } } return dp[shortstr.length]; }