【leetcode】1187. Make Array Strictly Increasing

题目如下：

解题思路：如果arr1[i]个元素需要交换的话，那么一定是和arr2中大于arr1[i-1]的所有值中最小的那个交换。在这个前提下，可以利用动态规划的思想来解决这个问题。首先对arr2去重排序，记dp[i][j] = v 表示使得arr1在0~i区间递增需要的最小交换次数为v，并且最后一个交换的操作是 arr1[i] 与 arr2[j]交换,由于存在不需要交换的情况，所以令 dp[i][len(arr2)]为arr1[i]为不需要交换。因为题目要保证递增，所以只需要关注arr1[i-1]与arr[i]的值即可，而两者之间只有以下四种情况：

最后的结果只需要求出四种情况的最小值即可。

代码如下：

class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        set<int> st(arr2.begin(), arr2.end());
        //arr2.clear();
        arr2.assign(st.begin(), st.end());
        //arr2.sort();
        sort(arr2.begin(), arr2.end());
        vector <vector<int>> dp ;for (int i =0;i< arr1.size();i++){
            vector<int> v2 (arr2.size()+1,2001);
            dp.push_back(v2);
        }
        for (int i = 0 ;i < arr2.size();i++){
            dp[0][i] = 1;
        }
        int res = 2001;
        int LAST_INDEX = arr2.size();
        dp[0][arr2.size()] = 0;
        //int ] = 0;
        for (int i =1 ;i < arr1.size();i++){
            for (int j = 0;j < arr2.size();j++){
                //only [i] exchange
                if (arr2[j] > arr1[i-1]){
                    dp[i][j] = min(dp[i][j],dp[i-1][LAST_INDEX] + 1);
                }
                //both [i] and [i-1] exchange
                if(j > 0){
                    dp[i][j] = min(dp[i][j],dp[i-1][j-1] + 1);
                }
                //only [i-1] change
                if (arr1[i] > arr2[j]){
                    dp[i][LAST_INDEX] = min(dp[i][LAST_INDEX],dp[i-1][j]);
                }
            }
            // no exchange
            if (arr1[i] > arr1[i-1]){
                dp[i][LAST_INDEX] = min(dp[i][LAST_INDEX],dp[i-1][LAST_INDEX]);
            }
        }
        for (int i = 0; i <= arr2.size();i++){
            res = min(res,dp[arr1.size()-1][i]);
        }
        return res == 2001 ? -1 : res;
    }
};