美图机器学习笔试

最长公共序列是给几个字符串求最长公共序列？

又不用实现，只是让写伪代码而已

第一题  模板元编程

美图测试岗位最后一道编程题就是最长公共序列，但是没AC过，心痛

。。错过美图了。哎

class LCS: def findLCS(self, A, n, B, m): # write code here self.n = n self.m = m self.A=A self.B=B self.dp={} return self.search(0, 0) def search(self, idxa, idxb): if (idxa >= self.n): return 0 if (idxb >= self.m): return 0 if(self.dp.has_key((idxa,idxb))): return self.dp[idxa,idxb] if (self.A[idxa] == self.B[idxb]): self.dp[idxa, idxb]=self.search(idxa + 1, idxb + 1) + 1 else: self.dp[idxa, idxb]=max(self.search(idxa + 1, idxb),self.search(idxa, idxb + 1)) return self.dp[idxa, idxb] LCS代码