leet.cs
Raw
int Foo(int[] arr1, int[] arr2) {
Array.Sort(arr2);
Dictionary<(int, int), int> dictionary = new Dictionary<(int, int), int>();
int Bar(int i, int prev) {
if (i == arr1.Length) return 0;
if (dictionary.ContainsKey((i, prev))) return dictionary[(i, prev)];
int cost = int.MaxValue;
if (arr1[i] > prev) {
cost = Bar(i + 1, arr1[i]);
}
int idx = Array.BinarySearch(arr2, prev + 1);
if (idx < 0) idx = ~idx;
if (idx < arr2.Length) {
cost = Math.Min(cost, 1 + Bar(i + 1, arr2[idx]));
}
dictionary[(i, prev)] = cost;
return cost;
}
int result = Bar(0, int.MinValue);
return result == int.MaxValue || result == int.MinValue ? -1 : result;
}
int[] arr1 = {1,5,3,6,7};
int[] arr2 = {1,6,3,3};
int result = Foo(arr1, arr2);
Console.WriteLine(result);
| 1 | int Foo(int[] arr1, int[] arr2) { |
| 2 | Array.Sort(arr2); |
| 3 | Dictionary<(int, int), int> dictionary = new Dictionary<(int, int), int>(); |
| 4 | |
| 5 | int Bar(int i, int prev) { |
| 6 | if (i == arr1.Length) return 0; |
| 7 | if (dictionary.ContainsKey((i, prev))) return dictionary[(i, prev)]; |
| 8 | |
| 9 | int cost = int.MaxValue; |
| 10 | if (arr1[i] > prev) { |
| 11 | cost = Bar(i + 1, arr1[i]); |
| 12 | } |
| 13 | |
| 14 | int idx = Array.BinarySearch(arr2, prev + 1); |
| 15 | if (idx < 0) idx = ~idx; |
| 16 | if (idx < arr2.Length) { |
| 17 | cost = Math.Min(cost, 1 + Bar(i + 1, arr2[idx])); |
| 18 | } |
| 19 | |
| 20 | dictionary[(i, prev)] = cost; |
| 21 | return cost; |
| 22 | } |
| 23 | |
| 24 | int result = Bar(0, int.MinValue); |
| 25 | return result == int.MaxValue || result == int.MinValue ? -1 : result; |
| 26 | } |
| 27 | |
| 28 | int[] arr1 = {1,5,3,6,7}; |
| 29 | int[] arr2 = {1,6,3,3}; |
| 30 | int result = Foo(arr1, arr2); |
| 31 | Console.WriteLine(result); |