python 代码
n, m = tuple(map(int, raw_input().split()))
a = raw_input()
b = raw_input()
dp = [[0 for j in range(m+1)]for i in range(2)]
for i in range(1, n+1):
for j in range(1, m+1):
if a[i-1] == b[j-1]:
dp[i%2][j] = dp[(i-1)%2][j-1]+1
else:
dp[i%2][j] = max(dp[i%2][j-1], dp[(i-1)%2][j])
print dp[n%2][m]
i%2为什么可以做,没看懂
这个根据滚动数组优化方法就能看出来,他每次转移只用到了上面一次的结果,很像滚动数组优化背包问题