假设我们有两个数组arr1和arr2，它们可以存储整数。我们必须找到使arr1严格增加所需的最小操作数。在这里，我们可以选择两个索引0 <= i <n和0 <= j <m并进行赋值arr1 [i] = arr2 [j]（n和m分别是arr1和arr2的大小）
如果我们不让3严格使数组arr1增大，则返回-1。
因此，如果输入类似于arr1 = [1,5,3,7,8]，arr2 = [1,3,2,5]，则输出将为1，因为我们可以将2替换为5，然后将数组将为[1,2,3,7,8]。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数resolve()，它将使用一个数组arr1，一个数组arr2，i，j，prev，一个2D数组dp，
如果i> = arr1的大小，则-
返回1
j = arr2 [j]和上层中arr2子数组的第一个元素
如果dp [i，j]不等于-1，则-
返回dp [i，j]
ret：= arr2的大小+ 1
如果prev <arr1 [i]，则-
ret：= ret和solve（arr1，arr2，i + 1，j，arr1 [i]，dp）的最小值
如果j <arr2的大小，则-
ret：= ret的最小值和1 + solve（arr1，arr2，i + 1，j，arr2 [j]，dp）
return dp [i，j] = ret
从主要方法中，执行以下操作-
排序数组arr2
n：= arr1的大小
m：= arr2的大小
定义一个大小为2005 x 2005的2D数组dp，并用-1填充
ret：= Solve(arr1,arr2,0,0,-inf,dp)
返回（如果ret> arr2的大小，则返回-1，否则ret-1）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<int>& arr1, vector<int>& arr2, int i, int j, int prev, vector<vector<int> >& dp){
if (i >= arr1.size())
return 1;
j = upper_bound(arr2.begin() + j, arr2.end(), prev) - arr2.begin();
if (dp[i][j] != -1)
return dp[i][j];
int ret = arr2.size() + 1;
if (prev < arr1[i]) {
ret = min(ret, solve(arr1, arr2, i + 1, j, arr1[i], dp));
}
if (j < arr2.size()) {
ret = min(ret, 1 + solve(arr1, arr2, i + 1, j, arr2[j], dp));
}
return dp[i][j] = ret;
}
int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2){
sort(arr2.begin(), arr2.end());
int n = arr1.size();
int m = arr2.size();
vector<vector<int> > dp(2005, vector<int>(2005, -1));
int ret = solve(arr1, arr2, 0, 0, INT_MIN, dp);
return ret > arr2.size() ? -1 : ret - 1;
}
};
main(){
Solution ob;
vector<int> v = {1,5,3,7,8}, v1 = {1,3,2,5};
cout << (ob.makeArrayIncreasing(v,v1));
}{1,5,3,7,8}, {1,3,2,5}输出结果
1