动态规划及LCS

LCS的python实现：
 1 #!/usr/bin/env python
 2 #-*- coding: utf-8 -*-
 3 import sys
 4 
 5 reload(sys)
 6 sys.setdefaultencoding('utf-8')
 7 
 8 
 9 class LCS(object):
10     """Long Common Subsequence算法
11     """
12     def __init__(self, str1, str2):
13         self.s1 = str1
14         self.s2 = str2
15         self.lcs = [['' for i in range(len(self.s2) + 1)] for j in range(len(self.s1) + 1)] # 另一种写法
16 
17     def get_lcs_len(self):
18         """递归计算lcs的长度
19         """
20         for i in xrange(len(self.s1) + 1):
21             for j in xrange(len(self.s2) + 1):
22                 if i == 0 or j == 0:
23                     self.lcs[i, j] = 0
24                 elif self.s1[i - 1] == self.s2[j - 1]:
25                     self.lcs[i, j] = self.lcs[i - 1][j - 1] + 1
26                 else:
27                     self.lcs[i, j] = max(self.lcs[i - 1][j], self.lcs[i][j - 1])
28         return self.lcs[len(self.s1), len(self.s2)]
29 
30     def get_lcs(self):
31         """递归计算lcs(直接获取lCS)
32         """
33         for i in xrange(len(self.s1) + 1):
34             for j in xrange(len(self.s2) + 1):
35                 if i == 0 or j == 0:
36                     self.lcs[i][j] = ''
37                 elif self.s1[i - 1] == self.s2[j - 1]:
38                     self.lcs[i][j] = self.lcs[i - 1][j - 1] + self.s1[i - 1]
39                 else:
40                     self.lcs[i][j] = self.lcs[i - 1][j] if len(self.lcs[i - 1][j]) > 
41                             len(self.lcs[i][j - 1]) else self.lcs[i][j - 1]
42         return self.lcs[len(self.s1)][len(self.s2)]
43 
44 
45 
46 if __name__ == '__main__':
47     s1 = 'abcdefgw'
48     s2 = 'bdfgegwe'
49     model = LCS(s1, s2)
50     print model.get_lcs()