給出兩個(gè)數(shù)列arr1和arr2，可以進(jìn)行操作將arr1[i]換為arr2[j]，求問(wèn)最少操作幾次可以讓arr1變?yōu)閲?yán)格遞增數(shù)列，如果不存在輸出-1，DP+二分搜索+memorization
參考了Discussion-> https://leetcode.com/problems/make-array-strictly-increasing/solutions/2290360/python-detailed-explanation-intution-explained-dp-clear-and-concise/
1 #1187
2 #Runtime: 4197 ms (Beats 25%)
3 #Memory: 193.2 MB (Beats 25%)
4
5 class Solution(object):
6 def makeArrayIncreasing(self, arr1, arr2):
7 """
8 :type arr1: List[int]
9 :type arr2: List[int]
10 :rtype: int
11 """
12 n1 = len(arr1)
13 n2 = len(arr2)
14 arr2.sort()
15 dp = {}
16
17 def cal(i, j, pre):
18 if i == n1:
19 return 0
20 if (i, j, pre) in dp:
21 return dp[(i, j, pre)]
22 k = bisect.bisect_right(arr2[j:], pre) + j
23 if k == n2:
24 ans = float('inf')
25 else:
26 ans = cal(i + 1, k + 1, arr2[k]) + 1
27 if arr1[i] > pre:
28 ans = min(ans, cal(i + 1, j, arr1[i]))
29 dp[(i, j, pre)] = ans
30 return ans
31
32 ans = cal(0, 0, -float('inf'))
33 return ans if ans != float('inf') else -1