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))
【感谢龙石为本站提供数据治理平台技术支撑 http://www.longshidata.com/pages/government.html】