LC-1187. 使数组严格递增（记忆化搜索==＞动态规划）

1187. 使数组严格递增

难度困难107

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

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

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

示例 1：

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

示例 2：

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

示例 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

记忆化搜索 => 动态规划

题解：https://leetcode.cn/problems/make-array-strictly-increasing/solution/zui-chang-di-zeng-zi-xu-lie-de-bian-xing-jhgg/

为方便描述，下文将 arr1 简记为 a ，arr2 简记为 b。问题等价于从 a 中找到一个最长严格递增子序列 lis，使得把不在 lis 中的元素替换成b中的元素后，a 是严格递增的，求不在 lis 中的元素个数的最小值

对于最长递增子序列问题 (或者一般的动态规划问题)，通常都可以用[选或不选]和[枚举选哪个]来启发思考。

方法一：选还是不选

例如 a=[0,4,2,2],b=[1,2,3,4]，假如 a[3] =2 换成了b[3] = 4,那么对于 a[2] =2 来说

• 选择不替换，问题变成[把[0,4] 替换成严格递增数组，且数组的最后一个数小于 2，所需要的最小操作数]。

• 选择替换，那么应该替换得越大越好，但必须小于 4 (因为a[3] 替换成了4)，那么换成3最佳，问题变成[把[0,4]替换成严格递增数组，且最后一个数小于 3，所需要的最小操作数].

  把从 a[0] 到 a[1] 的这段前缀替换成严格递增数组，且数组的最后一个数小于 pre，所需要的最小操作数。记为 dfs(i,pre)

记忆化搜索

class Solution {int[] a, b;Map<Integer, Integer> memo[];public int makeArrayIncreasing(int[] arr1, int[] arr2) {this.a = arr1;this.b = arr2;Arrays.sort(b);// 为了能二分查找，对b排序int n = a.length;memo = new HashMap[n];Arrays.setAll(memo,e -> new HashMap<>());// 假设 a[n-1] 右侧有个无穷大的数int ans = dfs(n-1, Integer.MAX_VALUE/2);return ans < Integer.MAX_VALUE/3 ? ans : -1;}/**例如 a=[0,4,2,2],b=[1,2,3,4]，假如 a[3] =2 换成了b[3] = 4,那么对于 a[2] =2 来说选择不替换，问题变成[把[0,4] 替换成严格递增数组，且数组的最后一个数小于 2，所需要的最小操作数]。选择替换，那么应该替换得越大越好，但必须小于 4 (因为a[3] 替换成了4)，那么换成3最佳，问题变成[把[0,4]替换成严格递增数组，且最后一个数小于 3，所需要的最小操作数]。*/// 把从 a[0] 到 a[1] 的这段前缀替换成严格递增数组，且数组的最后一个数小于 pre，所需要的最小操作数。记为 dfs(i,pre)public int dfs(int i, int pre){if(i < 0) return 0;if(memo[i].containsKey(pre)) return memo[i].get(pre);// 不替换int res = a[i] < pre ? dfs(i-1, a[i]) : Integer.MAX_VALUE/2;// 替换// 二分查找b中小于pre的最大数的下标 int k = lowerbound(b, pre) - 1; if(k >= 0) { // a[i]替换成小于 pre 的最大数res = Math.min(res, dfs(i-1, b[k]) + 1);}memo[i].put(pre, res);return res;}   // 返回大于等于key的第一个元素的下标public int lowerbound(int[] nums, int target){int left = 0, right = nums.length;while(left < right){int mid = (left + right) / 2;if(nums[mid] < target) left = mid + 1;else right = mid;}return left;}
}

方法二：枚举选哪个

在方法二中，我们把重点放在 s 上，关注哪些 a[i] 没有被替换，那么答案就是 n -length(lis)。

记忆化搜索

仿照最长递增子序列的状态定义，用 dfs(i) 表示以 a[i] 结尾的 lis 的长度，这里a[i] 没有被替换

• 枚举a[i] 左侧最近的没有被替换的元素a[j]，那么必须满足从 a[j+1] 到 a[i-1]的这段数组，能被替换成b中的元素，且替换后从a[j]到a[i] 是严格递增的。为了保证替换的元素互不相同，需要对 b去重。

设 b[k] 为 >=a[i] 的最小元素，注: 即使 b[k] 不存在也没关系，下面不会用到这个数

a[i -1] 最大可以替换成 b 中小于 a[i] 的最大元素，即 b[k - 1]，然后a[i - 2] 最大可以替换成 b[k - 2]，…，a[j +1] 最大可以替换成b[k-(i-j-1)]。

注: 从a[j+1]到 a[i-1]一共有i-j-1个数。
所以，只有满足 b[k -(i -j- 1)] >a[j]，才能完成替换操作。此时更新 dfs(i) = max(dfs(i), dfs(j) + 1)。
注: 要求k-(i-j-1)>= 0，也就是j>=i-k -1。

class Solution {int[] a, b, memo;int m;public int makeArrayIncreasing(int[] arr1, int[] arr2) {this.a = arr1;this.b = arr2;Arrays.sort(b);// 为了能二分查找，对b排序for(int i = 1; i < b.length; i++){if(b[m] != b[i]){b[++m] = b[i]; // 原地去重}}++m;int n = a.length;memo = new int[n+1]; // 0 表示还没有计算过int ans = dfs(n);return ans < 0 ? -1 : n + 1 - ans;}public int dfs(int i){if(memo[i] != 0) return memo[i];int x = i < a.length ? a[i] : Integer.MAX_VALUE;int k = lowerbound(b, m, x);int res = k < i ? Integer.MIN_VALUE : 0; // 小于 a[i] 的数全部替换if(i > 0 && a[i-1] < x) { // 无替换res = Math.max(res, dfs(i-1));} for(int j = i-2; j > i-k-1 && j >= 0; j--){if (b[k - (i - j - 1)] > a[j])// a[j+1] 到 a[i-1] 替换成 b[k-(i-j-1)] 到 b[k-1]res = Math.max(res, dfs(j));}return memo[i] = ++res; // 把 +1 移到这里，表示 a[i] 不变}// 返回大于等于key的第一个元素的下标public int lowerbound(int[] nums, int right, int target){int left = 0;while(left < right){int mid = (left + right) / 2;if(nums[mid] < target) left = mid + 1;else right = mid;}return left;}
}

翻译成递推

class Solution {public int makeArrayIncreasing(int[] a, int[] b) {int n = a.length, m = 0;Arrays.sort(b);// 为了能二分查找，对b排序for(int i = 1; i < b.length; i++){if(b[m] != b[i]){b[++m] = b[i]; // 原地去重}}++m;var f = new int[n + 1];for (int i = 0; i <= n; i++) {int x = i < n ? a[i] : Integer.MAX_VALUE;int k = lowerbound(b, m, x);int res = k < i ? Integer.MIN_VALUE : 0; // 小于 a[i] 的数全部替换if (i > 0 && a[i - 1] < x) // 无替换res = Math.max(res, f[i - 1]);for (int j = i - 2; j > i - k - 1 && j >= 0; --j)if (b[k - (i - j - 1)] > a[j])// a[j+1] 到 a[i-1] 替换成 b[k-(i-j-1)] 到 b[k-1]res = Math.max(res, f[j]);f[i] = res + 1; // 把 +1 移到这里，表示 a[i] 不替换}return f[n] < 0 ? -1 : n + 1 - f[n];    }// 返回大于等于key的第一个元素的下标public int lowerbound(int[] nums, int right, int target){int left = 0;while(left < right){int mid = (left + right) / 2;if(nums[mid] < target) left = mid + 1;else right = mid;}return left;}
}