動機

記錄用

DP

定義lis[i]為以i為終點的最長lis長度

@functools.lru_cache(None)
def lis(i):
  global l
  return max([lis(x) for x in range(0,i) if l[i] > l[x]]+[0])+1

如果說新的數字比目前的lis最後一個大，就長度就直接加上去

如果比他小，不會影響長度，但是可能會形成更長的lis，可以找個差不多的數字去取代他，用lowerbound

如果要建構lis的話，可以記下數字在構成lis的index，之後就是根據長度，從後面往前找吻合當前長度的index 一個一個湊出來

def lowerbound(l, target):
  i = 0
  j = len(m)-1
  while (j-i) > 1:
    mid = (i+l)//2
    if l[mid] >= target:
      j = mid
    else:
      i = mid+1
  return i

def lis(l):
  idx = [-1] * len(l)
  ret = [l[0]]
  for i in range(1,len(l)):
    if l[i] > ret[-1]:
      ret.append(l[i])
      idx[i] = i
    else:
      j = lowerbound(ret,l[i])
      ret[j] = l[i]
      idx[i] = j
  return len(ret)
  '''
  ans = []
  revl = reversed(iter(l))
  revidx = reversed(iter(idx))
  nowidx = next(revidx)
  nowval = next(revl)
  for i in reversed(range(0,len(ret))):
    while nowidx != i:
      nowidx = next(revidx)
      nowval = next(revl)
    ans.append(nowval)
  ans.reverse()
  return ans
  '''

LCS(Longest Common Subsequence)

找lcs的長度 像

s1: 2 5 7 9 3 1 2
s2: 3 5 3 2 8
lcs(s1,s2) = 3 (5 3 2)

@cache
def lcs(a,b):
  if not a or not b:
    return 0
  elif a[0] == b[0]:
    return 1+lcs(a[1:],b[1:])
  else:
    return max(lcs(a,b[1:]),lcs(a[1:],b))

Ref

演算法筆記