本题用状态机分类讨论比较容易理解,思路参考的 这个代码
dp[i][j] 表示arr1前i位数字保持升序所需要最少的交换次数, 其中arr1[i][0]表示arr1[i]不与arr2中任何数字交换的最少交换次数,arr1[i][j] (j>0)表示arr1[i]与arr2[j]交换后的最少交换次数。
状态机有3种转移方式:
1. arr1[i]不交换
dp[i][0] = min{dp[i-1][j]} (arr2[j] < arr1[i])
2. arr1[i]交换
2.1 arr1[i-1]不换
dp[i][j] = min{dp[i-1][j]} (arr2[j] > arr1[i-1])
2.2 arr1[i-1]换
dp[i][j] = dp[i-1][j-1] + 1
const int N = 2010;
class Solution {
public:
int dp[N][N];
void insertFront(vector<int>& arr, int x) {
reverse(arr.begin(), arr.end());
arr.push_back(x);
reverse(arr.begin(), arr.end());
}
int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
int n1 = arr1.size(), n2 = arr2.size();
insertFront(arr1, -1); insertFront(arr2, -1);
memset(dp, 0x3f, sizeof dp);
sort(arr2.begin(), arr2.end());
dp[1][0] = 0;
for (int i = 1; i <= n2; i++) dp[1][i] = 1;
for (int i = 2; i <= n1; i++) {
//arr1[i] unexchanged
if (arr1[i - 1] < arr1[i]) dp[i][0] = dp[i - 1][0];
for (int j = 1; j <= n2 && arr1[i] > arr2[j]; j++)
dp[i][0] = min(dp[i][0], dp[i - 1][j]);
//arr1[i] exchanged
for (int j = 1; j <= n2; j++) {
if (arr1[i - 1] < arr2[j])
dp[i][j] = min(dp[i][j], dp[i - 1][0] + 1);
if (j > 1)
dp[i][j] = arr2[j] == arr2[j - 1] ? dp[i][j - 1] : min(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
int ans = 1e9;
for (int i = 0; i <= n2; i++) ans = min(ans, dp[n1][i]);
return ans == 1e9? -1 : ans;
}
};