oa.py

# Time: O(max(len(arr), max(arr)))
# Space: O(N)

import collections

def common(arr1, arr2):
  if not arr1 or not arr2:
    return []

  c1, c2 = map(collections.Counter, [arr1, arr2])
  return sum([[num] * min(c1[num], c2[num]) for num in range(max(max(arr1), max(arr2)) + 1)], [])

print(common([3,1,2,2,1],[1,2,2,1,3]))
# >>> [1, 1, 2, 2, 3]


# 思路: 背包DP
#
# Time: O(k*n*m)
# Space: O(k*n) 可以利用滚动数组优化成O(n)
def rpg(n, m, k):
  dp = [[0] * (n + 1) for _ in range(k + 1)]
  dp[1] = [min(m+1, i) for i in range(1, n + 1)]

  for i in range(2, k+1):
    for j in range(1, n+1):
      dp[i][j] += sum(dp[i-1][j-w] for w in range(1, min(m, j)+1))
  return 1 - dp[-1][-1] / (m+1) ** k

第二个感觉不是太对？比如n=2，m=1，k=4的时候