Làm mảng tăng chặt trong C++

Giả sử chúng ta có hai mảng arr1 và arr2, có thể lưu trữ các số nguyên. Chúng ta phải tìm số phép toán tối thiểu cần thiết để làm cho arr1 tăng chặt. Ở đây, chúng ta có thể chọn hai chỉ số 0 <= i < n và 0 <= j < m và thực hiện gán arr1[i] = arr2[j] (n và m là kích thước của arr1 và arr2 tương ứng)

Nếu chúng ta không thể làm cho mảng arr1 tăng chặ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, khi đó mảng sẽ trở thành [1,2,3,7,8].

Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −

Định nghĩa hàm solve(), nhận mảng arr1, mảng arr2, i, j, prev, mảng 2D dp,
nếu i >= kích thước của arr1, thì −
- trả về 1
j = phần tử đầu tiên của mảng con của arr2 từ arr2[j] và upper
nếu dp[i, j] khác -1, thì −
- trả về dp[i, j]
ret := kích thước của arr2 + 1
nếu prev < arr1[i], thì −
- ret := min của ret và solve(arr1, arr2, i + 1, j, arr1[i], dp)
nếu j < kích thước của arr2, thì −
- ret := min của ret và 1 + solve(arr1, arr2, i + 1, j, arr2[j], dp)
trả về dp[i, j] = ret
Từ phương thức main, 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
Định nghĩa mảng 2D dp kích thước 2005 x 2005 và điền -1
ret := solve(arr1, arr2, 0, 0, -inf, dp)
trả về (nếu ret > kích thước của arr2, thì -1, ngược lại ret - 1)

Hãy xem 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}

Làm mảng tăng chặt trong C++

Ví dụ

Đầu vào

Đầu ra