动态规划

def dp(state):
  if state in memo: return memo[state]
  if base_case: return base
  memo[state] = best(dp(next_state) for choice in choices)
  return memo[state]

for i in range(1, n):
  current = choose_best(previous_states, a[i])
  shift(previous_states, current)

for item in items:
  for capacity in reversed(range(item, target + 1)):
    dp[capacity] = combine(dp[capacity], dp[capacity - item])

for i in range(1, m + 1):
  for j in range(1, n + 1):
    if a[i-1] == b[j-1]: match_transition()
    else: choose_from_neighbors()