在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，则-

list-style-type: square;">

• 返回dp [i，j]

• ret：= arr2的大小+ 1

• 如果prev <arr1 [i]，则-

list-style-type: square;">

• 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