在C ++中使数组严格增加
假设我们有两个数组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）
returndp[i，j]=ret
从主要方法中，执行以下操作-
排序数组arr2
n：=arr1的大小
m：=arr2的大小
定义一个大小为2005x2005的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