或者说是权力使用DP

1187. 使数组严格递增

给你两个整数数组 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

思路：
本题中的可行权力为替换元素，替换次数的范围是[0, n]，其中n = arr1.length
故可设计状态为f[i][j]表示考虑arr1的前i个元素，共进行j次替换使其严格递增的第i个元素的最小值
状态转移：
f[i][j] = min(f[i][j], f[i - 1][j]) if arr1[i] > f[i - 1][j]
f[i][j] = min(f[i][j], arr2[l]) if arr2[l] > f[i - 1][j - 1]

  1. class Solution {
  2.     public int makeArrayIncreasing(int[] a, int[] b) {
  3.         Arrays.sort(b);
  4.         int n = a.length, m = b.length;
  5.         int[][] f = new int[n + 1][n + 1];
  6.         for (int i = 0; i <= n; i++)
  7.             Arrays.fill(f[i], 0x3f3f3f3f);
  8.         f[0][0] = -0x3f3f3f3f;
  10.         for (int i = 1; i <= n; i++) {
  11.             for (int j = 0; j <= i; j++) {
  12.                 if (a[i - 1] > f[i - 1][j])
  13.                     f[i][j] = Math.min(f[i][j], a[i - 1]);
  14.                 if (j - 1 >= 0) {
  15.                     int t = f[i - 1][j - 1];
  16.                     int l = 0, r = m - 1;
  17.                     while (l < r) {
  18.                         int mid = l + r >> 1;
  19.                         if (b[mid] <= t)
  20.                             l = mid + 1;
  21.                         else r = mid;
  22.                     }
  24.                     if (b[l] > f[i - 1][j - 1])
  25.                         f[i][j] = Math.min(f[i][j], b[l]);
  26.                 }
  27.             }
  28.         }
  30.         int res = 0x3f3f3f3f;
  31.         for (int i = 0; i <= n; i++)
  32.             if (f[n][i] < res) {
  33.                 res = i;
  34.                 break;
  35.             }
  36.         return res == 0x3f3f3f3f ? -1 : res;
  37.     }
  38. }

1186. 删除一次得到子数组最大和

给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
注意，删除一个元素后，子数组 不能为空。

示例 1：
输入：arr = [1,-2,0,3] 输出：4 解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。
示例 2：
输入：arr = [1,-2,-2,3] 输出：3 解释：我们直接选出 [3]，这就是最大和。
示例 3：
输入：arr = [-1,-1,-1,-1] 输出：-1 解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。 我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。

提示：

  • 1 <= arr.length <= 105
  • -104 <= arr[i] <= 104

思路：
本题的可行权力为最多删除一个元素，目标是求最大连续子数组和
故状态表示可定义为：f[i][j]表示考虑前i个数，j == 0含义为以i结尾的非空最大连续子数组和，j == 1表示以i结尾的最多删除1个元素的最大连续子数组和
状态转移为：
初始化：f[i][0] = arr[0], f[i][1] = 0
f[i][0] = Math.max(f[i - 1][0], 0) + arr[i]
f[i][1] = Math.max(f[i - 1][0], f[i - 1][1] + arr[i])

  1. class Solution {
  2.     public int maximumSum(int[] arr) {
  3.         int n = arr.length;
  5.         int[][] f = new int[n][2];
  6.         f[0][0] = arr[0];
  7.         f[0][1] = 0;
  8.         int res = f[0][0];
  10.         for (int i = 1; i < n; i++) {
  11.             f[i][0] = Math.max(f[i - 1][0], 0) + arr[i];
  12.             f[i][1] = Math.max(f[i - 1][0], f[i - 1][1] + arr[i]);
  13.             res = Math.max(res, Math.max(f[i][0], f[i][1]));
  14.         }
  15.         return res;
  16.     }
  17. }

801. 使序列递增的最小交换次数

思路：
状态表示：f[i, 0]表示不交换第i个元素，且前i个元素保持单调递增的最少交换次数
f[i, 1]表示交换第i个元素，且前i个元素保持单调递增的最少交换次数
本题能行使的权利为是否交换
状态转移：
考虑到第i个元素是否交换只与第i - 1个元素是否交换有关
若A[i] > A[i - 1] && B[i] > B[i - 1]
f[i][0] = Math.min(f[i][0], f[i - 1][0])
f[i][1] = Math.min(f[i][1], f[i - 1][1] + 1)
若A[i] > B[i - 1] && B[i] > A[i - 1]
f[i][0] = Math.min(f[i][0], f[i - 1][1])
f[i][1] = Math.min(f[i][1], f[i - 1][0] + 1)
初始化：
f[0][0] = 0; f[0][1] = 1

  1. class Solution {
  2.     public int minSwap(int[] nums1, int[] nums2) {
  3.         int n = nums1.length;
  4.         int[][] f = new int[n][2];
  5.         for (int i = 0; i < n; i++)
  6.             Arrays.fill(f[i], 0x3f3f3f3f);
  7.         f[0][0] = 0;
  8.         f[0][1] = 1;
  10.         for (int i = 1; i < n; i++) {
  11.             if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
  12.                 f[i][0] = Math.min(f[i][0], f[i - 1][0]);
  13.                 f[i][1] = Math.min(f[i][1], f[i - 1][1] + 1);
  14.             }
  15.             if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
  16.                 f[i][0] = Math.min(f[i][0], f[i - 1][1]);
  17.                 f[i][1] = Math.min(f[i][1], f[i - 1][0] + 1);
  18.             }
  19.         }
  20.         return Math.min(f[n - 1][0], f[n - 1][1]);
  21.     }
  22. }