1187. Make Array Strictly Increasing

import math
import bisect

class Solution:
  def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
    # 从 arr2 中选取元素放到 arr1 中，让 arr1 严格递增
    # 返回所需的最小操作次数
    # 如果不行，返回 -1
    # 没办法用贪心，局部最优解不等于全局最优解
    # 所以需要动态规划
    # dp[i, j] 表示对 arr1 的第 i 个元素，操作 j 次，arr2 的最小值
    # 要么不换，则要有 arr1[i] > dp[i-1,j]，而 dp[i,j] = arr1[i]
    # 要么换，则要有某最小 k 使得 arr2[k] > dp[i-1,j-1]，而 dp[i,j] = arr2[k]
    # 最后只要返回 arr1[m] 中第一个不是 inf 的数字对应的 j 即可
    arr2 = sorted(set(arr2))
    m, n = len(arr1), len(arr2)
    # 最多可以有 min(m, n) 次操作，最少 0 次操作
    # 加上一个起始辅助元素，dp 总共有 m + 1 行
    dp = [[math.inf] * (min(m, n) + 1) for _ in range(m + 1)]
    # 起始辅助元素标记为 -inf
    dp[0][0] = -math.inf
    for i in range(1, m + 1):
      # 此处为 min(i, n) 因为目前只有 i 个元素，最多也就换 i 次
      # 实际运行时时间优化了不少
      for j in range(min(i, n) + 1):
        if arr1[i-1] > dp[i-1][j]:
          dp[i][j] = arr1[i-1]
        if j and dp[i-1][j-1] != math.inf:
          # arr2 从 arr2[j-1] 往后（含），大于 dp[i-1][i-1] 的第一个数
          # [[bisect]] 是 Python 内置的一个二分搜索包
          k = bisect.bisect_right(arr2, dp[i-1][j-1], j-1)
          # 可能超出 arr2 的范围，即 k = n
          # 不用担心太小，k = 0 意味着我们可以用 arr2 第一个元素操作
          if k < n:
            dp[i][j] = min(dp[i][j], arr2[k])
        if i == m and dp[i][j] != math.inf:
          return j
    return -1