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