leetcode1187 Make Array Strictly Increasing

思路：

暴力dp，dp[i][j]表示到第i个位置为止，构造一个以数字j为结尾的严格上升序列所需要的最小操作次数。

实现：

 1 class Solution
 2 {
 3 public:
 4     int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2)
 5     {
 6         int n = arr1.size(), m = arr2.size();
 7         sort(arr2.begin(), arr2.end());
 8         vector<map<int, int>> v(1);
 9         v[0][arr1[0]] = 0;
10         if (arr2[0] < arr1[0]) v[0][arr2[0]] = 1;
11         for (int i = 1; i < n; i++)
12         {
13             map<int, int> mp;
14             for (auto it: v[i - 1])
15             {
16                 if (arr1[i] > it.first)
17                 {
18                     if (!mp.count(arr1[i])) mp[arr1[i]] = INT_MAX;
19                     mp[arr1[i]] = min(mp[arr1[i]], it.second);
20                 }
21                 int p = upper_bound(arr2.begin(), arr2.end(), it.first) - arr2.begin();
22                 if (p != m)
23                 {
24                     if (!mp.count(arr2[p])) mp[arr2[p]] = INT_MAX;
25                     mp[arr2[p]] = min(mp[arr2[p]], it.second + 1);
26                 }
27             }
28             map<int, int> mp2;
29             int minn = INT_MAX;
30             for (auto it: mp)
31             {
32                 if (it.second >= minn) continue;
33                 minn = it.second;
34                 mp2[it.first] = it.second;
35             }
36             v.push_back(mp2);
37         }
38         int res = INT_MAX;
39         for (auto it: v[n - 1]) res = min(res, it.second);
40         return res == INT_MAX ? -1 : res;
41     }
42 }