1.最长上升子序列
对于一个数字序列，请设计一个复杂度为O(nlogn)的算法，返回该序列的最长上升子序列的长度，这里的子序列定义为这样一个序列U1，U2...，其中Ui < Ui+1，且A[Ui] < A[Ui+1]。 给定一个数字序列A及序列的长度n，请返回最长上升子序列的长度。 测试样例： [2,1,4,3,1,5,6],7 返回：4
方法1：O（n2）
生成一个新的列表b，b和输入列表a对应长度。b[t]表示a以a[t]为结尾的上升子序列长度。
# -*- coding:utf-8 -*- class AscentSequence: def findLongest(self, A, n): # write code here b=[]#存放相应位置最长子序列的长度 for i in range(len(A)):#循环a temp=A[i] b.append(1)#b赋初值1 for j in range(i):#对i之前数遍历，找到以a[i]结尾的子序列长度 if(A[i]>A[j] and b[j]+1>b[i]): b[i]=b[j]+1 result=max(b) return result
方法2.O(nlogn)
生成一个新的列表b，b[t]表示长度为t+1的子序列的结尾数字。
我们再举一个例子：有以下序列A[]=3 1 2 6 4 5 10 7，求LIS长度。
我们定义一个B[i]来储存可能的排序序列，len为LIS长度。我们依次把A[i]有序地放进B[i]里。（为了方便，i的范围就从1~n表示第i个数）
A[1]=3，把3放进B[1]，此时B[1]=3，此时len=1，最小末尾是3 ---注意这里的举例是从下标1开始的，方便理解，实际代码直接从0开始
A[2]=1，因为1比3小，所以可以把B[1]中的3替换为1，此时B[1]=1，此时len=1，最小末尾是1
A[3]=2，2大于1，就把2放进B[2]=2，此时B[]={1,2}，len=2
同理，A[4]=6，把6放进B[3]=6，B[]={1,2,6}，len=3
A[5]=4，4在2和6之间，比6小，可以把B[3]替换为4，B[]={1,2,4}，len=3
A[6]=5，B[4]=5，B[]={1,2,4,5}，len=4
A[7]=10，B[5]=10，B[]={1,2,4,5,10}，len=5
A[8]=7，7在5和10之间，比10小，可以把B[5]替换为7，B[]={1,2,4,5,7}，len=5
# -*- coding:utf-8 -*- class AscentSequence: def findLongest(self, A, n): # write code here b=[]#b位置上存储是下标位置-1（长度）的结尾数字 b.append(A[0])#先把第一个元素放进来 for i in range(1,len(A)): if(A[i]>b[-1]):#如果A大于b的最后一个数字，b直接追加 b.append(A[i]) else: for j in range(len(b)): if (A[i]<b[j]):#A中元素与b中元素比较，所以是nLogn的复杂度 b[j]=A[i]#相同长度的子序列，选择最小的那个 break#一定要跳出循环 return len(b)
参考：
http://blog.csdn.net/zhangyx_xyz/article/details/50949957
https://www.nowcoder.com/test/question/done?tid=10236396&qid=25104#summary
2.最长公共子序列长度
对于两个字符串，请设计一个高效算法，求他们的最长公共子序列的长度，这里的最长公共子序列定义为有两个序列U1,U2,U3...Un和V1,V2,V3...Vn,其中Ui<Ui+1，Vi<Vi+1。且A[Ui] == B[Vi]。 给定两个字符串A和B，同时给定两个串的长度n和m，请返回最长公共子序列的长度。保证两串长度均小于等于300。 测试样例： "1A2C3D4B56",10,"B1D23CA45B6A",12 返回：6
分析：
首先区别一下子串与子序列，子串要求是连续的而子序列不要求连续。例如ABCDEG字符串, ABC为子串，ADG为子序列。
设有两个字符串数组 str1【N】和str2【M】，构建二维数组DP【N】【M】,其中DP【i】【j】的含义：字符串str1【0……i】与str2【0……j】的公共子序列的长度。
我们来分析DP【i】【j】的来源，
1、首先DP【i】【j】的值不会小于DP【i-1】【j-1】,如果str1【i】==str2【j】，则DP【i】【j】 = DP【i-1】【j-1】+1。
2、如果str1【i】！= str2【j】，DP的来源于max( DP【i】【j-1】，DP【i-1】【j】)，
此时不用考虑DP【i-1】【j-1】，因为：
DP【i】【j-1】>=DP【i-1】【j-1】,
DP【i-1】【j】>=DP【i-1】【j-1】
( 没看明白可以这样考虑：
str1【0……i】与str2【0……j-1】 的公共子序列肯定不会比str1【0……i-1】与str2【0……j-1】的公共子序列小，
同理str1【0……i-1】与str2【0……j】的公共子序列肯定不会比str1【0……i-1】与str2【0……j-1】的公共子序列小。)
所以选取这两个最大一个即可。
（实际上分了三种情况讨论。。。）
明白DP【i】【j】的含义，以及DP【i】【j】的推导后，我们再来看如何构造DP【N】【M】数组。
1、首先构造第一行，
DP【0】【0……M-1】代表字符串str1【0……0】与str2【0……M-1】的最长公共子序列，
可以看出这一行的值，不为1就为0，
且当DP【0】【K】为1时（含义：str1【0】 ==str2【K】&&str1【0】！=str2【0……K-1】) DP【0】【K+1……M-1】均为1。
2、构造第一列，
DP【0……N-1】【0】代表str1【0……N-1】与str2【0……0】的最长公共子序列，
可以看出这一列的值同第一行一样，不为1就为0，
且当DP【K】【0】为1时（含义：str1【K】 ==str2【0】&&str1【0……K-1】！=str2【0】) DP【K+1……M-1】【0】均为1。
3、知道了第一行和第一列的值，可以根据求得其他所有矩阵中的值。
如果题目还让我们输出这个最长公共子序列呢？
构造DP【N】【M】之后，就可以根据DP【N】【M】来求得最长公共子序列。
1、首先从右下角开始，DP【N-1】【M-1】，如果str1【N-1】 == str2【M-1】 则说明str1【N-1】一定是最长公共子序列中的一个数，得记录下来
2、如果str1【N-1】 ！= str2【M-1】，则不用记录str1【N-1】或str2【M-1】，这时需要向上（DP【i-1】【j】）移动或者向左
（DP【i】【j-1】）移动，看这两个值哪个大，谁大往谁的方向移。（可以这样理解，既然我们这个点str1【N-1】与str2【M-1】不同，
但是此时最大递增子序列的长度应该是不变的，所以应该向DP【】【】值不变的方向移动，回想起我们在创建DP【】【】数组时，
当str1【N-1】 ！= str2【M-1】，DP【N-1】【M-1】的来源是左边和上边其中的较大值。所以应该向左边和上边中的较大值移动）
3、每到str1【K1】 == str2【K2】 记录下str1【k1】，不相等时，向左和上的较大值移动，直到DP【K1】【k2】==0终止。
参考：
http://blog.csdn.net/qq_27161673/article/details/52674898
https://www.nowcoder.com/test/question/done?tid=10236396&qid=25105#summary
# -*- coding:utf-8 -*- class LCS: def findLCS(self, A, n, B, m): # write code here #这里一定要注意的是，列表里边的m和n的顺序，一定要和下边for循环合拍，容易错 dp=[[0 for i in range(m+1)]for j in range(n+1)] for i in range(n): for j in range(m): if A[i]==B[j]: dp[i+1][j+1]=dp[i][j]+1 else: dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]) return dp[n][m]
3.最长公共子串
对于两个字符串，请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度)，求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,...Vn，
其中Ui + 1 == Ui+1,Vi + 1 == Vi+1，同时Ui == Vi。 给定两个字符串A和B，同时给定两串的长度n和m。 测试样例： "1AB2345CD",9,"12345EF",7 返回：4
下面是字符串21232523311324和字符串312123223445的匹配矩阵，前者为X方向的，后者为Y方向的。不难找到，红色部分是最长的匹配子串。通过查找位置我们得到最长的匹配子串为：21232
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
但是在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。通过改进矩阵的生成方式和设置标记变量，可以省去这部分时间。
0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
0 1 0 0 0 0 0 0 0 2 1 0 0 0 0
1 0 2 0 1 0 1 0 0 0 0 0 1 0 0
0 2 0 0 0 0 0 0 0 1 1 0 0 0 0
1 0 3 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 4 0 0 0 2 1 0 0 1 0 0 0
1 0 1 0 5 0 1 0 0 0 0 0 2 0 0
1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
0 0 0 2 0 0 0 2 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
当字符匹配的时候，我们并不是简单的给相应元素赋上1，而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置，在矩阵生成的过程中来判断当前生成的元素的值是不是最大的，据此来改变标记
量的值，那么到矩阵完成的时候，最长匹配子串的位置和长度就已经出来了。
# -*- coding:utf-8 -*- class LongestSubstring: def findLongest(self, A, n, B, m): # write code here dp=[[0 for i in range(m+1)]for j in range(n+1)] result=0 for i in range(n): for j in range(m): if A[i]==B[j]: dp[i+1][j+1]=dp[i][j]+1 result=max(result,dp[i+1][j+1]) return result
4.最小编辑代价
对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。 给定两个字符串A和B，及它们的长度和三种操作代价，请返回将A串变为B串所需要的最小代价。保证两串长度均小于等于300，且三种代价值均小于等于100。 测试样例： "abc",3,"adc",3,5,3,100 返回：8
分析：
同样，我们令a=len(A),b=len(B)，我们可以申请一个dp——(a+1)*(b+1)的列表。用来保存我们的中间结果。
dp=[i][j]表示A[i-1]到B[j-1]的编辑距离；
dp[0][0]=0；
dp[i][0]表示A[i-1]到B[0]的编辑距离，要不停的删除；
dp[0][j]表示A[0]到B[j-1]的编辑距离，要不停的添加；
如何求dp[i][j]？首先dp[i][j]表示的是将A[i-1]变成B[j-1]。三个途径。dp[i-1][j-1] dp[i][j-1] dp[i-1][j]
1.当A[i-1]==B[j-1]时，不用编辑，dp[i][j]=dp[i-1][j-1]；
2.当A[i-1]！=B[j-1]时，dp[i][j]=min(dp[i-1][j-1]+c2, dp[i][j-1]+c0,dp[i-1][j]+c1)。
下面我们解释第二种情况中min中的三个子编辑的来源。
要求dp[i][j]，我们可以直接把A[i-1]修改成B[j-1]，这里就是dp[i-1][j-1]+c2 ；
要求dp[i][j]，我们可以把A[i-1]改成B[j-2]，然后再添加一个B[j-1]，这里A[i-1]改成B[j-2]的代价已经求出来了，就是dp[i][j-1]，所以总的代价是dp[i][j-1]+c0；
要求dp[i][j]，我们可以把A[i-2]改成B[j-1]，然后再删除A[i]，因为我们的终极目标就是要得到B[j-1]，dp[i-1][j]已经做到了，那么我们可以把多出来的元素A[i]删掉即可。
最后我们从这三个当中找一个最小的编辑代价即可。
# -*- coding:utf-8 -*- class MinCost: def findMinCost(self, A, n, B, m, c0, c1, c2): # write code here dp=[[0 for i in range(m+1)] for j in range(n+1)] for i in range(1,m+1): dp[0][i]=dp[0][i-1]+c0 for j in range(1,n+1): dp[j][0]=dp[j-1][0]+c1 for j in range(1,n+1): for i in range(1,m+1): if A[j-1]==B[i-1]: dp[j][i]=dp[j-1][i-1] else: dp[j][i]=min(dp[j-1][i-1]+c2,dp[j-1][i]+c1,dp[j][i-1]+c0) return dp[-1][-1]
注意：1.i和j分别对应谁，这个比较容易出错；2.不要把min写成max
5.字符串交错组成
对于三个字符串A，B，C。我们称C由A和B交错组成当且仅当C包含且仅包含A，B中所有字符，且对应的顺序不改变。请编写一个高效算法，判断C串是否由A和B交错组成。 给定三个字符串A,B和C，及他们的长度。请返回一个bool值，代表C是否由A和B交错组成。保证三个串的长度均小于等于100。 测试样例： "ABC",3,"12C",3,"A12BCC",6 返回：true
分析：
假设str1的长度为N，str2的长度为M，生成(N+1)*(M+1)的dp矩阵，为什么是N+1,M+1，因为我们需要在字符串的开头添加一个空字符的特殊情况，dp[i][j]的值代表aim[0…i+j-1]能否被str1[0…i-1]和str2[0…j-1]交错组成，dp[i][j]的值计算如下：
矩阵的第一行表示能否只用str2[0…j-1]交错组成aim[0…j-1]，如果str2[0…j-1]等于aim[0…j-1]，则令dp[0][j] = True，否则为False
矩阵的第一列同上，如果str1[0…i-1]等于aim[0…i-1]，则令dp[i][0] = True，否则为False
矩阵的其余位置由以下情况决定：
1）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
2）dp[i][j-1]代表aim[0…i+j-2]能否被str2[0…j-2]和str1[0…i-1]交错组成，如果可以，那么如果再有str2[j-1]等于aim[i+j-1]，说明str2[j-1]又可以作为交错组成aim[0…i+j-1]的最后一个字符。令dp[i][j] = True
3）如果上述情况不满足，令dp[i][j] = False
# -*- coding:utf-8 -*- class Mixture: def chkMixture(self, A, n, B, m, C, v): # write code here #if A == None or B == None or C == None or len(A)+len(B) != len(C): #return False dp = [[False for i in range(len(B)+1)] for j in range(len(A)+1)] dp[0][0] = True for i in range(1, len(A)+1): if A[i-1] != C[i-1]: break dp[i][0] = True for j in range(1, len(B)+1): if B[j-1] != C[j-1]: break dp[0][j] = True for i in range(1, len(A)+1): for j in range(1, len(B)+1): if (dp[i-1][j] == True and A[i-1] == C[i+j-1]) or (dp[i][j-1] == True and B[j-1] == C[i+j-1]): dp[i][j] = True return dp[-1][-1]
注意：dp矩阵只是存储过程，并非真正的步骤，字体中粉色1）的话，dp[i][j]就是判断str1[i-1]和str2[j-1]能否表示str3[i+j-1]，如果dp[i-1][j]代表aim[0…i+j-2]能否被str1[0…i-2]和str2[0…j-1]交错组成，所以问题的关键是str1[i-1]是不是和str3[i+j-1]相等。2）同理。
千万要理解dp矩阵的含义。
方法2：用递归
class Mixture: def chkMixture(self, A, n, B, m, C, v): # write code here if(v == 0): return true if(n == 0): return B == C if(m == 0): return A == C if(A[0]==C[0] and B[0]!=C[0]): return self.chkMixture(A[1:],n-1,B,m,C[1:],v-1) elif(B[0]==C[0] and A[0]!=C[0]): return self.chkMixture(A,n,B[1:],m-1,C[1:],v-1) elif(B[0]==C[0] and A[0]==C[0]): return self.chkMixture(A[1:],n-1,B,m,C[1:],v-1) or self.chkMixture(A,n,B[1:],m-1,C[1:],v-1) else: return False
参考：
http://m.blog.csdn.net/qq_34342154/article/details/77151959
http://www.cnblogs.com/sunp823/p/5601406.html