?solution1：
????????最开始的想法，递归，for循环target，如果arr里面没有则加1，如果有递归，两种情况。1、插入新的target为[1,3]，新的arr为匹配到的位置后面的部分[9，4，1，2，3，4]，这里还有一个细节，就是有可能arr有相同的数。2、不插入，加1，新的target[1,3]，arr保持不变。然后对两种结果取最小值
count =0
clist =[]
def compc(target,arr,count):
for i in range(len(target)):
num = target[i]
loc = np.where(arr==num)
if(len(loc[0]) ==0):
count = count+1
else:
if(i==len(target)-1):
return count
clistt = []
countb = compc(target[i + 1:], arr, count + 1)
clistt.append(countb)
for j in range(len(loc[0])):
a = int(loc[0][j])
arrt = arr[a:]
counta = compc(target[i+1:], arrt,count)
clistt.append(counta)
count= min(clistt)
clist.append(count)
return count
return count
c = compc(target,arr,count)
print(clist)
if len(clist)>1:
c = min(clist)
print(c)很显然，空间复杂度和时间复杂度严重超标。
?solution2：
? ? ? ? 看了一眼解析，哦，找最长公共子序列，那就动态规划，就去看了一眼动态规划的逻辑，直接暴力复现
? ? ? ? 这块的关键是转换了思想，在arr里寻找包含的target里的元素以及对应的位置，我感觉我下次还是想不到。。。。
#转换为最长递增子序列，暴力动态规划
pos =[]
tmp =0
for i in range(len(arr)):
if arr[i] in target:
al = np.where(target==arr[i])
pos.append(al[0])
dp = np.ones(len(pos))
for i in range(len(pos)):
val = pos[i]
for j in range(i):
if(pos[j]<val):
dp[i]=max(dp[i],dp[j]+1)
c =len(target) -int(max(dp))
print(c)很显然还是超时。
?solution3：
? ? ? ? 这时，target的特点就要突出了，递增序列，意味着寻找递增的子序列，那么第二层for循环就可以简化了，这个逻辑，pos里面的元素可以通过对比大小来进行删除，将for循环换成了while（这里用了二分法来插入）
#二分法 动态规划
pos =[]
for i in range(len(arr)):
if arr[i] in target:
al = np.where(target==arr[i])
pos.append(al[0])
dp = []
dp.append(pos[0])
tmp =1
for i in range(1,len(pos)):
if(dp[len(dp)-1]<pos[i]):
dp.append(pos[i])
else:
l=0
r = len(dp)-1
loc =r
while(l<=r):
mid = (l+r)//2
if(dp[mid]>=pos[i]):
loc = mid
r = mid-1
else:
l = mid+1
dp[loc] =pos[i]
c =len(target) -len(dp)
print(c)?发现还是超时，，emmm，又看了一眼解析，发现一个for循环和第二个for循环完全可以合并啊，用了bisect.bisect_left二分查找的库，我寻思库能比我写的快点？然后又又又试了一下
?solution4：
#两个for循环可以合并
pos = []
dp = []
for i in range(len(arr)):
if arr[i] in target:
al = np.where(target == arr[i])
# pos.append(al[0])
idx = al[0]
if (len(dp) == 0 or idx > dp[len(dp) - 1]):
dp.append(idx)
else:
site = bisect.bisect_left(dp, idx)
if site < len(dp):
dp[site] = idx
else:
dp.append(idx)
c = len(target) - len(dp)????????还是不行，还是超时，然后我把答案里面的c++版本拷进去提交了一下，是真的快，应该是python本身的局限性吧。看起来逻辑是一样的，行吧，思想最重要，就到这吧。
学了忘，忘了学，学了还得忘，忘了学，学了忘，忘了还得学。