python最長共通サブシーケンス動的計画問題の実現
1286 ワード
pythonで動的計画方法で2つのシーケンスの最長共通サブシーケンスを求めることを書きました.コードのどこに問題があるか教えてください.
# -*- coding: utf-8 -*-
# author:Huangyuliang
#
# a,b
import numpy as np
def lcs_len(a,b):
n = len(a)
m = len(b)
p = n+1
q = m+1
c = np.zeros((p,q))
val = c.copy()
for i in range(1,p):
for j in range(1,q):
if a[i-1] == b[j-1]:
c[i,j] = c[i-1,j-1] + 1
val[i,j] = 0 #
elif c[i-1,j] >= c[i,j-1]:
c[i,j] = c[i-1,j]
val[i,j] = 1 #
else:
c[i,j] = c[i,j-1]
val[i,j] = 2 #
k = int(c[n,m]) # k
print "k =",k
G = range(k+1) # G
while k>0:
if val[n,m]==1:
n-=1
elif val[n,m]==2:
m-=1
else:
G[k] = a[n-1]
k-=1
n-=1
m-=1
return G[1:]
a,b = [1,2,3,5,7,8,9],[1,2,3,4,5,9]
h = lcs_len(a,b)
print h
：
k = 5
h = [1,2,3,5,9]