Làm cho mảng tăng lên nghiêm ngặt trong C ++

Giả sử chúng ta có hai mảng arr1 và arr2, chúng có thể lưu trữ các số nguyên. Chúng ta phải tìm số lượng phép toán tối thiểu cần thiết để làm cho arr1 tăng lên một cách nghiêm ngặt. Tại đây, chúng ta có thể chọn hai chỉ số 0 <=i

Nếu chúng ta caPending-3 không làm cho mảng arr1 tăng nghiêm ngặt, thì trả về -1.

Vì vậy, nếu đầu vào giống như arr1 =[1,5,3,7,8], arr2 =[1,3,2,5], thì đầu ra sẽ là 1, vì chúng ta có thể thay thế 5 bằng 2, sau đó mảng sẽ là [1,2,3,7,8].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm giải quyết (), điều này sẽ nhận một mảng arr1, một mảng arr2, i, j, trước, một dp mảng 2D,

• if i> =size of arr1, then -

  • trả lại 1

• j =phần tử đầu tiên của mảng con của arr2 từ arr2 [j] trở lên

• nếu dp [i, j] không bằng -1 thì -

  • trả về dp [i, j]

• ret:=kích thước của arr2 + 1

• nếu trước

  • ret:=tối thiểu ret và giải quyết (arr1, arr2, i + 1, j, arr1 [i], dp)

• nếu j

  • ret:=tối thiểu ret và 1 + giải quyết (arr1, arr2, i + 1, j, arr2 [j], dp)

• return dp [i, j] =ret

• Từ phương thức chính, thực hiện như sau -

• sắp xếp mảng arr2

• n:=kích thước của arr1

• m:=kích thước của arr2

• Xác định một dp mảng 2D có kích thước 2005 x 2005 và điền vào giá trị này bằng -1

• ret:=giải quyết (arr1, arr2, 0, 0, -inf, dp)

• return (nếu ret> kích thước của arr2 thì -1, nếu không thì ret - 1)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{1,5,3,7,8}, {1,3,2,5}

Đầu ra

1