CodeTestcaseTest ResultTest Result1187. Make Array Strictly Increasing

public class Solution {
    public int MakeArrayIncreasing(int[] arr1, int[] arr2) {
        Array.Sort(arr2);
        int answer = Dfs(0, -1, arr1, arr2);
        return answer < 2001 ? answer : -1;
    }
    Dictionary<(int, int), int> dp = new Dictionary<(int, int), int>();
    private int Dfs(int i, int prev, int[] arr1, int[] arr2) {
        if (i == arr1.Length) {
            return 0;
        }
        var key = (i, prev);
        if (dp.ContainsKey(key)) {
            return dp[key];
        }
        int cost = 2001;
        if (arr1[i] > prev) {
            cost = Dfs(i + 1, arr1[i], arr1, arr2);
        }
        int idx = Array.BinarySearch(arr2, prev + 1);
        if (idx < 0) {
            idx = ~idx;
        }
        if (idx < arr2.Length) {
            cost = Math.Min(cost, 1 + Dfs(i + 1, arr2[idx], arr1, arr2));
        }
        dp[key] = cost;
        return cost;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MakeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        sort(arr2.begin(), arr2.end());
        int answer = Dfs(0, -1, arr1, arr2);
        return answer < 2001 ? answer : -1;
    }
    unordered_map<(int, int), int> dp = new unordered_map<(int, int), int>();
    private int Dfs(int i, int prev, vector<int>& arr1, vector<int>& arr2) {
        if (i == arr1.size()) {
            return 0;
        }
        var key = (i, prev);
        if (dp.count(key)) {
            return dp[key];
        }
        int cost = 2001;
        if (arr1[i] > prev) {
            cost = Dfs(i + 1, arr1[i], arr1, arr2);
        }
        int idx = Array.BinarySearch(arr2, prev + 1);
        if (idx < 0) {
            idx = ~idx;
        }
        if (idx < arr2.size()) {
            cost = min(cost, 1 + Dfs(i + 1, arr2[idx], arr1, arr2));
        }
        dp[key] = cost;
        return cost;
    }
}

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int MakeArrayIncreasing(int[] arr1, int[] arr2) {
        Arrays.sort(arr2);
        int answer = Dfs(0, -1, arr1, arr2);
        return answer < 2001 ? answer : -1;
    }
    HashMap<(int, int), int> dp = new HashMap<(int, int), int>();
    private int Dfs(int i, int prev, int[] arr1, int[] arr2) {
        if (i == arr1.length) {
            return 0;
        }
        var key = (i, prev);
        if (dp.containsKey(key)) {
            return dp[key];
        }
        int cost = 2001;
        if (arr1[i] > prev) {
            cost = Dfs(i + 1, arr1[i], arr1, arr2);
        }
        int idx = Array.BinarySearch(arr2, prev + 1);
        if (idx < 0) {
            idx = ~idx;
        }
        if (idx < arr2.length) {
            cost = Math.min(cost, 1 + Dfs(i + 1, arr2[idx], arr1, arr2));
        }
        dp[key] = cost;
        return cost;
    }
}

Algorithm

Сначала отсортируйте массив arr2 и инициализируйте хэш-таблицу dp для хранения промежуточных результатов. Определите функцию dfs(i, prev), которая вычисляет минимальное количество операций для сортировки массива arr1, начиная с индекса i, при условии, что предыдущий элемент равен prev. Если результат для (i, prev) уже существует в dp, то просто верните сохраненное значение.

Внутри функции dfs инициализируйте переменную cost значением float('inf'). Если arr1[i] больше, чем prev, обновите значение cost результатом вызова dfs(i + 1, arr1[i]). Используйте бинарный поиск, чтобы найти индекс idx наименьшего значения в arr2, которое больше prev. Если такой индекс существует, обновите значение cost результатом минимального значения между текущим значением cost и 1 + dfs(i + 1, arr2[idx]).

После всех вычислений обновите dp[(i, prev)] значением cost и верните cost. В конце вызовите dfs(0, -1) и верните его значение, если оно не равно float('inf'); в противном случае верните -1.

😎