0. 模版技巧总结
DP数组边界条件
在很多的题目中，动态数组依赖上边和左边的数，dp[i][j] = dp[i-1][j]+dp[i][j-1]，这就使得我们不得不处理复杂的边界情况，单独的为第一行和第一列，乃至dp[0][0]去计算数值，非常麻烦！
比如在最长公共子序列问题中，要单独处理边界，原因就是后续的传递公式中dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1);，必须要考虑i和j要大于0。
int[][] dp = new int[M][N];
dp[0][0] = str1.charAt(0) == str2.charAt(0) ? 1 : 0;
// 第一列
for (int i = 1; i < M; ++i){
dp[i][0] = Math.max(dp[i-1][0], str1.charAt(i) == str2.charAt(0) ? 1 : 0);
}
// 第一行
for (int j = 1; j < N; ++j){
dp[0][j] = Math.max(dp[0][j-1], str1.charAt(0) == str2.charAt(j) ? 1 : 0);
} 一个巧妙的技巧就是初始化DP数组时多增加一层。这样第一行和第一列默认就是0，通常实际情况也是0，比如最长公共子序列问题中，多增加一层后，第一行和第一列就被看作是空字符和空字符的公共子序列。
// 设置dp数组，多增加一层
int M = str1.length()+1;
int N = str2.length()+1;
int[][] dp = new int[M][N];
// 直接计算
for (int i = 1; i < str1.length()+1; i++){
for (int j = 1; j < str2.length()+1; j++){
if (str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
}else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[M-1][N-1]; 为什么多增加一层就是对的呢？因为我们从第二行，列开始处理，就避免了之前i，j必须大于0的问题。而且我们仔细分析之前两种方法，其中前一种中，单独处理第一行列的方式其实就是和后续大循环中的思想是一样的，只是一种特殊边界的妥协！所以这类题目都可以用这种方法来避免处理边界。
比如：最长公共子序列，最长公共子串
但是有一些方法不能使用这个技巧，因为它们的边界处理和大循环中的不一致！
比如：UniquePath（机器人路径）问题中，边界条件就要单独处理。
UPI中第一行和第一列都是1，因为只能有一种走法。
UPII中第一行和第一列，一旦遇到障碍物后，后续的点都不可到达都为0。
1. 经典DP
最长升序子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。经典单子串问题
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
解题思路:
解题思路的动画可以参考liweiwei1419
方法一：
动态规划的思想，设置一个dp数组，它表示，dp[i]是以arr[i]结尾的最长升序子序列的长度。很自然的dp[0]就初始化为1，因为一个数也是长度为一的升序子序列。如何求dp[i]就是，在arr[0~i-1]中遍历所有的数，如果有arr[j]小于arr[i]，其中j～[0,i-1]，那么它对应dp[j]就可以和arr[i]组成一个新的升序子序列且长度是dp[j]+1，求里面最长的那个就是dp[i]。
最后我们会得到一个和arr长度一样的dp数组，它是每个以arr[i]结尾的最长升序子序列的长度，我们期望的是这个dp数组的最大值，而不是最后一个值！我们要返回一个int数不是数组。
算法复杂度，时间：O(Nˆ2), 空间O(N)
public static int lengthOfLIS(int[] nums) {
// 边界情况
if(nums == null || nums.length == 0){
return 0;
}
// 设置dp数组，含义是: dp[i]，以arr[i]结尾的最长升序子序列的长度
// dp[i] 初始值为1
// dp[i] = Max{ arr[从0到(i-1)中]所有比arr[i]小的dp[j]+1 }
int len = nums.length;
int[] dp = new int[len];
int max = 0;
for (int i=0; i<len; i++){
// 初始值为1，就算你是最大的，你的LIS也至少是1
dp[i] = 1;
for (int j=0; j<i; j++){
if (nums[j] < nums[i]){
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
max = Math.max(max, dp[i]);
}
return max;
} 方法二：
贪心和二分查找的思想，重新定义目标值，构造一个辅助数组tails，tails[i] 表示长度为i+1的LIS最小结尾数，tails的有效范围从0-0开始。基于贪心的思想，如果已经得到的上升子序列的结尾的数越小，遍历的时候后面接上一个数，就会有更大的可能性构成一个更长的上升子序列。
更新tails数组的思想是，end是tails的左边界限，从0开始。
- 遍历nums数组，若nums[i]检查到，ends有效区中没有比它大的数，则有效区加1，tails[end+1]=nums[i]
- 若nums[i]不是ends有效区中最大的，那么在tails数组中找到>=它最左的位置[不妨设为k]，替换掉它，它就是新的长度为k+1的LIS最小结尾数，结合下面的例子更好理解，上面的链接中还有动图。
这个方法能把时间复杂度降到O(NlogN)，这非常的重要，有个笔试题就是只能这个复杂度才能通过！它快的原因就是在查找排序数组中>=x的最左位置时，采用了模版的二分查找。细细评味，这个查找>=它最左的位置，就是找到第一个比他大的数，快速的替换他，满足贪心策略。
给定数组[10, 9, 2, 5, 3, 7, 101, 18]，开始遍历数组，
- 初始化tails数组tails[0]=10，这表示长度为1的LIS最小结尾数是10
- 接下来遇到了9，它的插入位置就是0，把10替换掉，这表示长度为1的LIS最小结尾数是9
- 同理，遇到2时就有tails[0]=2
- 遇到5时，比tails中都大，则end有效区+1，tails[1]=5,这表示长度为2的LIS最小结尾数是5
- 遇到3，把5更新了，tails[1]=3
- 遇到7，比tails中都大，则end有效区+1，tails[2]=7,这表示长度为3的LIS最小结尾数是7
- 同理101，tails[3]=101
- 最后是18，把101更新了，tails[3]=18
- 最后返回end有效区+1，就是最长的长度
public static int getDpWithBinarySearch(int[] nums){
// 利用贪心，二分法 和 辅助数组让时间复杂度降低到 O(NlogN)
// 辅助数组 tails, tails[i] 表示长度为i+1的LIS最小结尾数，tails的有效范围从0-0开始
// end是tails的左边界限
// 若nums[i]检查到，ends有效区中没有比它大的数，则有效区加1，tails[end+1]=nums[i]
// 遍历完所有的nums后，end+1就是LIS的长度
// 二分法的三个变量
int l = 0;
int r = 0;
int m = 0;
// dp数组
int[] dp = new int[nums.length];
// 存放最小结尾数的数组，暂时有效区是0-0
int[] tails = new int[nums.length];
// 表示有效区右边界
int end = 0;
dp[0] = 1;
tails[0] = nums[0];
for (int i=1; i<nums.length; i++){
if (nums[i] > tails[end]){
// 有效区加一
end++;
tails[end] = nums[i];
}else {
// 二分找到在ends中最左边的 >= nums[i]的位置
// 也就是在为nums[i]找插入替代的位置！
l = 0;
r = end;
while(l<= r){
m = l + ((r - l) >> 1);
if (tails[m] >= nums[i]){
r = m - 1;
}else{
l = m + 1;
}
}
// 最后返回的是 l or r+1 就是<=nums[i] 最左边的位置也就是插入位置
tails[l] = nums[i];
}
dp[i] = end + 1;
}
end++;
//也可以return end;
return dp[dp.length-1];
} 最长公共子序列
LC Nr. 1143
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
解题思路:dp[i][j]的含义是str1[0..i]与str2[0..j]的最长公共子序列的长度。矩阵dp第一列即dp[0..M-1][0]，dp[i][0]的含义是str1[0..i]与str2[0]的最长公共子序列长度。
str2[0]只有一个字符，所以dp[i][0]最大为1。如果str1[i]==str2[0]，令dp[i][0]=1，一旦dp[i][0]被设置为1，之后的dp[i+1..M-1][0]也都为1。
dp[i][j]的只来自于三种可能。
- 可能是
dp[i-1][j]，代表str1[0..i-1]与str2[0..j]的最长公共子序列长度。 - 可能是
dp[i][j-1]，代表str1[0..i]与str2[0..j-1]的最长公共子序列长度。 - 如果
str1[i]==str2[j]，还可能是dp[i-1][j-1]+1。这个如果成立是最大的
// 得到dp数组
public static int[][] getDP(String str1, String str2){
if (str1==null || str2==null || str1=="" || str2==""){
return null;
}
// 通过dp数组得到最长的长度
int M = str1.length();
int N = str2.length();
int[][] dp = new int[M][N];
dp[0][0] = str1.charAt(0) == str2.charAt(0) ? 1 : 0;
// 第一列
for (int i = 1; i < M; ++i){
dp[i][0] = Math.max(dp[i-1][0], str1.charAt(i) == str2.charAt(0) ? 1 : 0);
}
// 第一行
for (int j = 1; j < N; ++j){
dp[0][j] = Math.max(dp[0][j-1], str1.charAt(0) == str2.charAt(j) ? 1 : 0);
}
// 普通位置: 三种可能性
for (int i=1; i<M; ++i){
for (int j=1; j<N; ++j){
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
if (str1.charAt(i) == str2.charAt(j)){
dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1);
}
}
}
return dp;
} 上面方法得到的是DP数组，最后结果在DP数组的最右下角。但是上面的方法要单独的处理第一行和第一列很繁琐，根据之前介绍的技巧，分析可知，第一行列的逻辑和大循环其实都一致，只是妥协了边界。下面的方法，新增加一行列，这代表空字符，结果都是0。图片来自labuladong
方法二：技巧行增加一行列
public static int getDP2(String str1, String str2){
// 参考力扣上的东哥的做法，不用特别计算第一列和第一层的数，但是dp数组的尺寸要加1
if (str1==null || str2==null || str1.length()==0 || str2.length()==0){
return 0;
}
// 设置dp数组
int M = str1.length()+1;
int N = str2.length()+1;
int[][] dp = new int[M][N];
// 直接计算
for (int i = 1; i < str1.length()+1; i++){
for (int j = 1; j < str2.length()+1; j++){
if (str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
}else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[M-1][N-1];
} 方法二改进：空间压缩
DP[i][j]的取值，与上方，左方，和斜上面有关，因此可以用滚动数组，只计算上下数组的相对数量关系就可以递推出答案。
public static int getDP3(String str1, String str2){
// 参考力扣上的东哥的做法，不用特别计算第一列和第一层的数，但是dp数组的尺寸要加1
// 在getDP2的基础上 空间压缩 力扣上性能提升！
if (str1==null || str2==null || str1.length()==0 || str2.length()==0){
return 0;
}
// 设置dp数组
int M = str1.length()+1;
int N = str2.length()+1;
int[] pre = new int[N];
int[] cur = new int[N];
// 直接计算
for (int i = 1; i < M; i++){
for (int j = 1; j < N; j++){
if (str1.charAt(i-1) == str2.charAt(j-1)){
cur[j] = pre[j-1] + 1;
}else {
cur[j] = Math.max(pre[j], cur[j-1]);
}
}
pre = cur.clone();
}
return cur[N-1];
} 最长公共子串的长度
给定两个字符串str1和str2，返回两个字符串的最长公共子串。
示例1:
str1="1AB2345CD"，str2="12345EF"，返回"2345"。
解题思路:
参考我敬爱的左程云老师的“程序员代码面试指南：最优解第二版”。
最核心的思想就是，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。
比如str1="A12E4B"，str2="CD12F4"，dp[3][4]的含义是在必须把str1[3](即'E')和str2[4](即'F')当作公共子串最后一个字符的情况下，公共子串最长能有多长。这种情况下根本不能构成公共子串，所以dp[3][4]为0。
public static int getLengthOfLCStr(String text1, String text2){
// dp[i][j]的含义是:
// 在必须把str1[i]和str2[j]当作公共子串最后一个字符的情况下，公共子串最长能有多长。
if (text1==null || text2==null || text1=="" || text2==""){
return 0;
}
int M = text1.length();
int N = text2.length();
int[][] dp = new int[M][N];
// 第一列的初始化
for(int i=0; i<M; i++){
if (text1.charAt(i) == text2.charAt(0)){
dp[i][0] = 1;
}
}
// 第一行的初始化
for (int j=0; j<N; j++){
if (text1.charAt(0) == text2.charAt(j)){
dp[0][j] = 1;
}
}
int max = 0;
// 从左向右 从上向下计算
for (int i=1; i<M; i++){
for (int j=1; j<N; j++){
if (text1.charAt(i) == text2.charAt(j)){
dp[i][j] = dp[i-1][j-1] + 1;
}
max = Math.max(max, dp[i][j]);
}
}
return max;
} 方法二：技巧性的增加一行列
观察分析第一种方法，DP数组的递推就是根据对角线元素，所以额外的增加一行一列，它的物理含义就是“空字符串”，值都是0，这样后续的从第一个字符算起的时候，就可以直接计算不用处理边界情况了。
public static int getLCStrLength(String str1, String str2){
if (str1 == null || str1 == "" || str2 == null || str2 == ""){
return 0;
}
int rows = str1.length()+1;
int cols = str2.length()+1;
int[][] dp = new int[rows][cols];
int len = 0;
for (int i = 1; i < rows; i++){
for (int j = 1; j < cols; j++){
if(str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
len = Math.max(len, dp[i][j]);
}
}
}
return len;
} 方法二改进：空间压缩的思路是基于矩形对角线，计算比较复杂。
我们注意到计算每一个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，如果str1[i]! =str2[j]，那么位置(i，j)的值为0。计算后将len更新成位置(i，j)的值，然后计算下一个位置，即(i+1，j+1)位置的值。依次计算下去就可以得到斜线上每个位置的值，然后算下一条斜线。用全局变量max记录所有位置的值中的最大值。此处引用左老师的书，非常好一定要买来看看！
对角线遍历方法的循环方式非常奇特，首先是行变量row控制最大的循环，从0开始，
内层循环中，先控制对角线方向递增，就是(i,j)在不越界的情况下变成(i+1, j+1)。当越界后，就是外层循环的递增条件，每次都是col减一，直到col等于0时换成每次row加一，直到row>=行数, 循环结束。
public static String getLCStrWithSpaceCompress(String str1, String str2){
if (str1==null || str2==null || str1=="" || str2==""){
return null;
}
// str1是较短的字符串 str2是最长的字符串
int rows = 0;
int cols = str2.length()-1;
// 记录子串长度的最大值
int max = 0;
// 最长子串的最后下标
int end = 0;
// 从最右上角开始，先是rows=0，cols递减，当cols=0后，rows递增，最后推出循环
while(rows < str1.length()){
int i = rows;
int j = cols;
// 长度临时变量, 记录每条对角线的情况
int len = 0;
// 控制一条斜线遍历
while (i<str1.length() && j<str2.length()){
if (str1.charAt(i)!=str2.charAt(j)){
len = 0;
}else{
len++;
}
// 寻找最大值
if (len > max){
max = len;
end = i;
}
++i;
++j;
}
// 遍历完一条对角线了
if (cols > 0){
cols--;
}else {
rows++;
}
}
return str1.substring(end-max+1, end+1);
} 最长公共子串输出
给定两个字符串str1和str2，返回两个字符串的最长公共子串, 输出较短字符串中先出现的那个。
解题思路:
根据之前的分析, 采用动态规划的思路计算的DP[i][j]，表示以str1[i],str[j]结尾的公共子串的长度, 当某个DP[i][j]最大时，其i就表示最长公共子串在str1中结尾的下标，再计算出长度，就可以在str1中还原出最长子串且保证是第一个，因此str1是较短的字符串，str2较长的。
此外要注意的是在利用技巧增加一行一列后，要注意i,j的含义。还有java的库函数str1.substring(startIndex, endIndex), 是获取子串从startIndex开始，到endIndex结束。。
public static String getLCStr(String text1, String text2){
// 优先从较短字符串中返回 最长公共子串
if (text1==null || text2==null || text1=="" || text2==""){
return null;
}
int rows = text1.length();
int cols = text2.length();
// 多加一行就不用判断特殊情况了
int[][] dp = new int[rows+1][cols+1];
// 记录最长子串的长度和结束下标
int max = 0;
int end = 0;
// 要注意这里 i,j 的含义
// dp[i][j] 是 text1中第i字符 对 text2中j字符
for (int i=0; i<rows; i++){
for (int j=0; j<cols; j++){
if (text1.charAt(i) == text2.charAt(j)){
dp[i+1][j+1] = dp[i][j] + 1;
}
if (dp[i+1][j+1] > max){
max = dp[i+1][j+1];
end = i;
}
}
}
// 要注意这里 i,j 的含义
// dp[i][j] 是 text1中第i+1字符 对 text2中j+1字符
for (int i=1; i<=rows; i++){
for (int j=1; j<=cols; j++){
if (text1.charAt(i-1) == text2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1] + 1;
}
if (dp[i][j] > max){
max = dp[i][j];
end = i-1;
}
}
}
// 子串从end开始计算，一共max长度，所以起始字符是 str[end-max+1]
// end+1是结束下表，是左闭右开区间，所以实际取str[end]，和函数性质有关是exclusive
return text1.substring(end-max+1, end+1);
} 2. 线性DP
3. 匹配DP
编辑距离
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符，代价为insertCost-ic
删除一个字符，代价为deleteCost-dc
替换一个字符，代价为replaceCost-rc
解题思路：
参考左老师的算法书，程序员代码面试指南:IT名企算法与数据结构题目最优解
关键在于DP数组的定义，DP[i][j]表示把字符串str1[0...i-1]编辑成str2[0...j-1]的最小代价，如果每种操作的代价都是1，也就是最小操作数。
dp[0][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*j。
其他位置按照从左到右，再从上到下来计算，dp[i][j]的值只可能来自以下四种情况。
当str1[i-1]==str2[j-1]时，由于遍历到了i和j，先把str1[0~i-2]编辑成str2[0~j-2]，其编辑代价是dp[i-1][j-1]，由于当前两个结尾字符相同，因此无需做任何操作即可得到，dp[i][j]=dp[i-1][j-1]。
当str1[i]!=str2[j]时，可以进行的操作有3个:
① 替换操作:
先把str1[0~i-2]编辑成str2[0~j-2]，由于只是当前位置的字符不匹配，进行替换操作后两者变得相同，所以此时dp[i][j] = dp[i-1][j-1]+ rc
② 删除操作:
如果把str1[0~i-2]编辑成str2[0~j-1]，此时多出了str1[i-1]位置的一个字符，应把它删除掉，才能使此时str1和str2整体匹配，因此此时dp[i][j] = dp[i-1][j] + dc
③ 插入操作:
如果把str1[0~i-1]编辑成str2[0~j-2]，但是str1长度不够，此时只需要在str[i-1]后面插入一个与str2[j-1]相同的字符，使得编辑后的str1和str2能匹配上，且长度一样了，所以此时dp[i][j] = dp[i][j-1] + ic
由于题目所要求的是要最少的操作数，所以需要在这三个操作中选取一个最小的值赋格当前的dp[i][j]。代码如下：
/*
* min edit cost
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @param ic int整型 insert cost
* @param dc int整型 delete cost
* @param rc int整型 replace cost
* @return int整型
*/
public static int minEditCost (String str1, String str2, int ic, int dc, int rc) {
// write code here
// word1为空，编辑word2.length()次的插入
if (str1.length() == 0) return str2.length() * ic;
// word2为空，编辑word1.length()次的删除
if (str2.length() == 0) return str1.length() * dc;
int rows = str1.length() + 1;
int cols = str2.length() + 1;
int[][] dp = new int[rows][cols];
// 第一行表示: "" 编辑成 word2[0~j-1]，都是插入操作
for (int j = 1; j < cols; j++){
dp[0][j] = j * ic;
}
// 第一列表示: word1[0~i-1] 编辑成 ""，都是删除操作
for (int i = 1; i < rows; i++){
dp[i][0] = i * dc;
}
for (int i = 1; i < rows; i++){
for (int j = 1; j < cols; j++){
if (str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
continue;
}else { // 替换操作
dp[i][j] = dp[i-1][j-1] + rc;
}
// 删除
dp[i][j] = Math.min(dp[i][j], dp[i-1][j] + dc);
// 插入
dp[i][j] = Math.min(dp[i][j], dp[i][j-1] + ic);
}
}
return dp[rows-1][cols-1];
} 空间压缩技巧，不是这个题目的重点。以前的空间压缩都是上方和左方的点，可以通过滚动数组解决，在这个题目中还有额外的左上角的点，所以需要一个额外的变量，并且主要空间压缩时，要选取要选择循环的方向，让短序列作为完成序列，长序列作为目标序列，让目标序列编辑成完成序列，这样只需要短序列长度的数组的额外空间，并遍历长序列长度的次数。
这里展示的是每个修改都是等代价的，如果不是的话，在交换长短序列时，如果目标序列发生改变，要注意把插入代价ic和删除代价dc交换一下即可。
public static int minDistanceWithSpaceCompress (String word1, String word2) {
// 洗数据，有空字符串的情况
if (word1.length()==0){
// 执行word2长度的插入操作
return word2.length();
}
if (word2.length()==0){
// 执行word1长度的删除操作
return word1.length();
}
// 空间压缩，要选择循环的方向，让短序列作为完成序列，长序列作为目标序列，让目标序列变成完成序列
// 这样只需要短序列长度的数组，并遍历长序列长度的次数
char[] ch1 = word1.toCharArray();
char[] ch2 = word2.toCharArray();
char[] longWord = ch1.length >= ch2.length ? ch1 : ch2;
char[] shortWord = ch1.length < ch2.length ? ch1 : ch2;
int[] dp = new int[shortWord.length + 1];
// 初始化：短序列的第一次遍历，是针对str1是空序列
for (int i = 1; i < dp.length; i++){
// i * insertCost: 空序列变成str2[1....end]
dp[i] = i;
}
// 以往的空间压缩都是，依赖与上方和左方元素，这次多了一个左上方，需要额外一个变量记录
for (int i = 1; i <= longWord.length; i++){
// 临时变量记录左上角的值
int corner = dp[0];
// 竖直方向遍历的初始化：i*deleteCost
dp[0] = i;
for (int j = 1; j <= shortWord.length; j++){
// 记录下dp[j]，也就是上方数据temp = dp[i-1][j]
int temp = dp[j];
if (longWord[i-1] == shortWord[j-1]){
// corner = dp[i-1][j-1]
dp[j] = corner;
continue;
}else {
// 替换
dp[j] = corner + 1;
}
// 插入操作: dp[j-1]->dp[i][j-1]
// dp[i][j-1] + insertCost
dp[j] = Math.min(dp[j], dp[j-1] + 1);
// dp[i-1][j] + deleteCost
dp[j] = Math.min(dp[j], temp + 1);
corner = temp;
}
}
return dp[shortWord.length];
} 4. 区间DP
5.其他问题
无重复字符的最长子串
Nr.3
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
解题思路:
利用哈希表记录每个出现的字符以其下标，当遇到重复的字符时，先判断重复的字符是否在left左指针的范围内，如果在，left更新到以前重复字符的下一个位置，如果不在，更新重复字符在哈希表中的下标记录，每次比较最大长度。
left就相当于统计“不重复子串长度的有效计算区”的边界，当在此区域内，新遍历的字符没有出现过(在哈希表里无记录)，则不重复子串的长度加1，如果出现了重复的字符(在哈希表里有记录)，有可能此记录是“上次left区里面”的旧字符，对于新left区来说是不重复的，因此要判断重复的记录与left的关系。
比如字符串:"abcddbcefga",当遍历到第二个d的时候，left此时在index=0的位置，查表可知被重复的d在index=3，因此left更新到index+1=4的位置，之前的长度到4，是目前最长的；
d在哈希表中更新到4，并开始继续遍历，长度并随之回归到1，之后遇到重复的'b','c','a'都会因为
没有大于left，而不会产生影响, 最终返回长度7(dcbcefga)。
代码:
public static int lengthOfLangestSubString( String str) {
if (str==null || str.length()==0){
return 0;
}
// 左指针
int left = 0;
int maxLength = 0;
// 字母记录表
HashMap<Character, Integer> CharMap = new HashMap<>();
// 遍历字母
for(int i=0; i<str.length(); i++){
// 如果有重复的字符，如果是在当前的有效区间内，则更新left
// 比如: abcddbcdefga 最后一个a，是在哈希表中重复的，如果不设置left，并不判断它与left的范围，会错误的导致left更新到2
if (CharMap.containsKey(str.charAt(i)) && CharMap.get(str.charAt(i)) >= left){
left = CharMap.get(str.charAt(i)) + 1;
}
// 添加新的字符，更新他们的value
CharMap.put(str.charAt(i), i);
maxLength = Math.max(maxLength, i-left+1);
} 
京公网安备 11010502036488号