ทำให้อาร์เรย์เพิ่มขึ้นอย่างเข้มงวดใน C++

ให้อาร์เรย์ arr1 และ arr2 ต้องหาจำนวนการดำเนินการน้อยที่สุดเพื่อทำให้ arr1 เพิ่มขึ้นอย่างเข้มงวด (strictly increasing) สามารถเลือกดัชนี i ใน arr1 และ j ใน arr2 กำหนด arr1[i] = arr2[j]

หากทำไม่ได้คืน -1

เช่น arr1=[1,5,3,7,8], arr2=[1,3,2,5] เอาต์พุต=1 แทนที่ 5 ด้วย 2 ได้ [1,2,3,7,8]

วิธีแก้ − ใช้ DP + Binary Search (upper_bound) บน arr2 ที่เรียงแล้ว Memoization สถานะ (i, j, prev)

ตัวอย่าง

#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(), 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}