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代码