- Leetcode 第 110 场双周赛 Problem D 2809. 使数组和小于等于 x 的最少时间（DP 好题）
- 题目
- 给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒，对于所有下标 0 <= i < nums1.length ，nums1[i] 的值都增加 nums2[i] 。操作 完成后 ，你可以进行如下操作：
- 选择任一满足 0 <= i < nums1.length 的下标 i ，并使 nums1[i] = 0 。
- 同时给你一个整数 x 。
- 请你返回使 nums1 中所有元素之和 小于等于 x 所需要的 最少 时间，如果无法实现，那么返回 -1 。
- 1 <= nums1.length <= 10 ^ 3
- 1 <= nums1[i] <= 10 ^ 3
- 0 <= nums2[i] <= 10 ^ 3
- nums1.length == nums2.length
- 0 <= x <= 10 ^ 6
- 解法
- DP+贪心+正难则反：
- 第 1 步：
- 每个 nums1[i] 置为 0，超过一次不如仅最后一次置为 0，
- 可知对于 nums1[i] 一样大，且不会影响其他 nums1，
- 因此时间最多就是 nums1.len、超过则无意义，
- 第 2 步：
- 问题转化为经过最少 s 秒且 s <= nums1.len，使得 nums3 = nums2[x]*(s-1) + nums2[y]*(s-2) + … + nums2[z]*0 + nums1[a] + …，nums3.len = nums1.len
- nums3 总和 sum(nums3) 小于等于 x 时，最小的 s 就是答案，否则答案就是 -1，
- 同时不可能推出 s 单调性，因此无法二分答案，
- 第 3 步：
- 正面直接求最小值无法想到什么贪心策略，如果使用 DP 则第 j+1 秒会影响前 j 秒的数据，因为每秒每个元素会加上 nums2，不满足无后效性，
- 正难则反：
- 求经过 s 秒最多可以减少多少
- 总数 sum(nums1) + s*sum(nums2) 减去即可
- 第 4 步：
- 动规状态：dp[i][j] 为前 i 个数经过 j 秒最多可以减少多少，注意 i>=j，
- 初始化 dp[i][0]=0，即前 i 个数不经过任何时间则无法减少
- 第 5 步：
- 转移方程：dp[i][j]=max(dp[i-1][j], dp[i-1][j-1] + nums1[i-1]+j*nums2[i-1])，
- 即第 i 个数经过 j 秒是否删除的最大值，取决于是否需要再第 j 秒清理掉第 i 个元素
- 此时 DP 无后效性，因为第 i+1 个数不会影响前 i 个数的更新，
- 同时需要满足减少 j 个元素的最大值、等于减少前（i-1 个元素中选 j-1 个元素）的最大值加第 i 个元素，
- 可以观察减少的是 nums1[i-1]+j*nums2[i-1]，由于前 j 秒等价于选 j 个元素，此时 nums1 顺序无所谓，j 固定升序、保证 j*nums2[i-1] 最大需要使 nums2 升序（nums1 跟随排序）
- 第 6 步：
- 最后结果就是枚举秒数 j=[0,nums1.len]，sum(nums1) + j * sum(nums2) - dp[nums1.len][j] <= x，找到最小的 j，没有则返回 -1
- 空间压缩：由于 dp[i][j] 仅与 dp[i-1][j]、dp[i-1][j-1] 有关，因此可以使用一维 dp[j] 倒序处理
- 时间复杂度：O(n ^ 2)，空间复杂度：O（n）
- 代码
public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {if (nums1 == null || nums2 == null || nums1.size() != nums2.size() || nums1.size() <= 0) {return -1;}int n = nums1.size();int sumNums1 = nums1.stream().mapToInt(Integer::intValue).sum();int sumNums2 = nums2.stream().mapToInt(Integer::intValue).sum();
List<Pair<Integer, Integer>> numsPair = new ArrayList<>(n);for (int i = 0; i < n; i++) {numsPair.add(new Pair<>(nums2.get(i), nums1.get(i)));}Collections.sort(numsPair, (o1, o2) -> o1.getKey() - o2.getKey());
int[] dp = new int[n + 1];for (int i = 1; i < n + 1; i++) {for (int j = i; j >=1; j--) {dp[j] = Math.max(dp[j], dp[j-1] + numsPair.get(i-1).getValue() + j * numsPair.get(i-1).getKey());}}
int res = -1;for (int j = 0; j <= n; j++) {if (sumNums1 + j * sumNums2 - dp[j] <= x) {res = j;break;}}return res;}
