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