## 暴力算法

import random

def lcs_recursive(arr1, arr2, left, right):
if left >= len(arr1) or right >= len(arr2):
return 0

max_len = 0
for i in range(left, len(arr1)):
for j in range(right, len(arr2)):
if arr1[i] == arr2[j]:
length = lcs_recursive(arr1, arr2, i + 1, j + 1)
max_len = max(max_len, length + 1)
return max_len

def lcs_bruteforce(arr1, arr2):
return lcs_recursive(arr1, arr2, 0, 0)


## 动态规划

def lcs_dp(arr1, arr2):
dp = [[0 for j in range(len(arr2) + 1)] for i in range(len(arr1) + 1)]
for i in range(len(arr1) - 1, -1, -1):
for j in range(len(arr2) - 1, -1, -1):
if arr1[i] == arr2[j]:
dp[i][j] = dp[i + 1][j + 1] + 1
else:
dp[i][j] = max(dp[i][j + 1], dp[i + 1][j])
return dp[0][0]


## 测试

arr1 = [3, 0, 2, 1, 4]
arr2 = [0, 1, 2, 3, 4]
print(lcs_bruteforce(arr1, arr2))
print(lcs_dp(arr1, arr2))

for i in range(0, 10):
arr1 = [random.randint(0, 9) for i in range(20)]
arr2 = [random.randint(0, 9) for i in range(20)]
result1 = lcs_bruteforce(arr1, arr2)
result2 = lcs_dp(arr1, arr2)
if result1 != result2:
print(result1, result2)

3
3


import timeit
import random

def test_lcs_bruteforce():
length = 30
arr1 = [random.randint(0, 9) for i in range(length)]
arr2 = [random.randint(0, 9) for i in range(length)]
lcs_bruteforce(arr1, arr2)

def test_lcs_dp():
length = 30
arr1 = [random.randint(0, 9) for i in range(length)]
arr2 = [random.randint(0, 9) for i in range(length)]
lcs_dp(arr1, arr2)

print(timeit.timeit(test_lcs_bruteforce, number=2, setup='from __main__ import test_lcs_bruteforce'))
print(timeit.timeit(test_lcs_dp, number=2, setup='from __main__ import test_lcs_dp'))

12.163799556001322
0.0012101709944545291

动态规划的速度比暴力算法快太多了！