如何用Python实现动态规划求解最长公共子序列长度？
- 内容介绍
- 文章标签
- 相关推荐
本文共计320个文字，预计阅读时间需要2分钟。
pythondef zuichanggonggongzixulie(s1, s2): len1=len(s1) len2=len(s2) dp=[[0 for _ in range(len2+1)] for _ in range(len1+1)] for i in range(1, len1+1): for j in range(1, len2+1): if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1] + 1 return dp[len1][len2]
def zuichanggonggongzixulie(s1,s2): """计算s1与s2的最长公共子序列""" len1=len(s1) len2=len(s2) dparray=[[0 for _ in range(len1+1)]for _ in range(len2+1)] #构建基础上加1，首行首列都为0，某一个字符串为空 print("dp初始二维数组为：") for i in dparray: print(i) for i in range(1,len1+1): #设len1为行，len2为列 注意：i从1到len1(遍历应从0-4) for j in range(1,len2+1): if s1[i-1]==s2[j-1]: #若当前两字母对比相等，在长度都减一的串比较结果上加1(当前位置左上的位置结果+1) dparray[i][j]=dparray[i-1][j-1]+1 else: #若当前两字母对比不相等，取各减小一个长度的比较最小值（取当前位置的左位置和当前位置的上位置中的最大值） #参考：(abc和ac)---(ab和acd)=>(abc和acd)结果等同于前两者较大值 dparray[i][j]=max(dparray[i-1][j],dparray[i][j-1]) print("dp最终二维数组为：") for i in dparray: print(i) return dparray[len1][len2] str1="ABCBDCS"str2="BDCADCD"print(zuichanggonggongzixulie(str1,str2))
本文共计320个文字，预计阅读时间需要2分钟。
pythondef zuichanggonggongzixulie(s1, s2): len1=len(s1) len2=len(s2) dp=[[0 for _ in range(len2+1)] for _ in range(len1+1)] for i in range(1, len1+1): for j in range(1, len2+1): if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1] + 1 return dp[len1][len2]
def zuichanggonggongzixulie(s1,s2): """计算s1与s2的最长公共子序列""" len1=len(s1) len2=len(s2) dparray=[[0 for _ in range(len1+1)]for _ in range(len2+1)] #构建基础上加1，首行首列都为0，某一个字符串为空 print("dp初始二维数组为：") for i in dparray: print(i) for i in range(1,len1+1): #设len1为行，len2为列 注意：i从1到len1(遍历应从0-4) for j in range(1,len2+1): if s1[i-1]==s2[j-1]: #若当前两字母对比相等，在长度都减一的串比较结果上加1(当前位置左上的位置结果+1) dparray[i][j]=dparray[i-1][j-1]+1 else: #若当前两字母对比不相等，取各减小一个长度的比较最小值（取当前位置的左位置和当前位置的上位置中的最大值） #参考：(abc和ac)---(ab和acd)=>(abc和acd)结果等同于前两者较大值 dparray[i][j]=max(dparray[i-1][j],dparray[i][j-1]) print("dp最终二维数组为：") for i in dparray: print(i) return dparray[len1][len2] str1="ABCBDCS"str2="BDCADCD"print(zuichanggonggongzixulie(str1,str2))