使数组严格递增

发表于 更新于 分类于

    1187. 使数组严格递增

    给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。

    每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1[i] = arr2[j]。

    如果无法让 arr1 严格递增，请返回 -1。

    示例 1：

    ```txt

    输入：arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]

    输出：1

    解释：用 2 来替换 5，之后 arr1 = [1, 2, 3, 6, 7]。

    ```

    示例 2：

    ```txt

    输入：arr1 = [1,5,3,6,7], arr2 = [4,3,1]

    输出：2

    解释：用 3 来替换 5，然后用 4 来替换 3，得到 arr1 = [1, 3, 4, 6, 7]。

    ```

    示例 3：

    ```txt

    输入：arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]

    输出：-1

    解释：无法使 arr1 严格递增。

    ```

    提示：

    • 1 <= arr1.length, arr2.length <= 2000

    • 0 <= arr1[i], arr2[i] <= 10^9

题目

1187. 使数组严格递增

给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。

每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1[i] = arr2[j]。

如果无法让 arr1 严格递增，请返回 -1。

示例 1：

1
2
3
输入：arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
输出：1
解释：用 2 来替换 5，之后 arr1 = [1, 2, 3, 6, 7]。

示例 2：

1
2
3
输入：arr1 = [1,5,3,6,7], arr2 = [4,3,1]
输出：2
解释：用 3 来替换 5，然后用 4 来替换 3，得到 arr1 = [1, 3, 4, 6, 7]。

示例 3：

1
2
3
输入：arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
输出：-1
解释：无法使 arr1 严格递增。

提示：

  • 1 <= arr1.length, arr2.length <= 2000
  • 0 <= arr1[i], arr2[i] <= 10^9

题解

方法一：

思路

我们令dp[i][j]为将第i个数改为arr2[j]使得序列升序的代价（j<m）,令dp[i][m]是不改变第i个数使得序列升序的代价。所求答案是min{dp[i-1][]}

对于每次状态转移需维护最小值，所以初始化所有状态为无穷大，再预先计算初始状态dp[0][]，即只有一个数的序列改变需要一次操作，不改变不需要操作，dp[0][j] = 1, 0<=j<m，dp[0][m] = 0。

对于状态的转移有四种情况。

在改变第i个时，需要一次操作次数。

  • dp[i][j]由dp[i-1][m]+1转移而来，条件是arr2[j] > arr1[m]
  • dp[i][j]由dp[i-1][c]+1, 0<=c<j转移而来，实际上是由dp[i][j-1]与dp[i-1][j-1]+1转移, (dp[i][j] = min{dp[i-1][0...j-1]+1} = min{dp[i-1][0...j-2]+1, dp[i-1][j-1]+1} = min{dp[i][j-1], dp[i-1][j-1]+1})

在不改变第i个时，不需要操作次数。

  • dp[i][m]由dp[i-1][m]转移而来，条件是arr1[i] > arr1[i-1]
  • dp[i][m]由dp[i-1][j]转移而来, 条件是arr1[i] > arr2[j]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int dp[2005][2005]; // dp[i][j] 第i个数改为j变成升序的代价，dp[i][m]不改第i个数变升序的代价。
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        memset(dp, 0x3f, sizeof(dp));
        sort(arr2.begin(), arr2.end());
        arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
        // for (int i:arr2) cout << i <<" ";
        int n = arr1.size(), m = arr2.size();
        for (int i=0; i<m; i++) {
            dp[0][i] = 1;
        }
        dp[0][m] = 0;
        for (int i=1; i<n; i++) {
            //i不变由i-1不变 转移
            if (arr1[i]>arr1[i-1]) dp[i][m] = min(dp[i][m], dp[i-1][m]);
            //i不变由i-1变 转移
            for (int j=0; j<m; j++) {
                if (arr2[j] < arr1[i]) dp[i][m] = min(dp[i][m], dp[i-1][j]);
            }
            //i变由i-1不变 转移
            for (int j=0; j<m; j++) {
                if (arr2[j] > arr1[i-1]) dp[i][j] = min(dp[i][j], dp[i-1][m]+1);
            }
            //i变由i-1变 转移
            for (int j=1; j<m; j++) {
                dp[i][j] = min({dp[i][j], dp[i][j-1], dp[i-1][j-1]+1});
            }
            // for (int j=0; j<=m; j++) {
            //     cout << dp[i][j] << " ";
            // } cout << endl;
        }
        // int ans = INF;
        // for (int i=0; i<=m; i++) ans = min(ans, dp[n-1][i]);
        // return ans == INF ? -1 : ans;
        int ans = min(dp[n-1][m-1], dp[n-1][m]);
        return ans==INF?-1:ans;
    }
};