核心思想

对于一个具体的题目，方法运行的指令条数不能超过10^7 ~ 10^8规模，否则就会超时那么就可以利用这个条件：

1、想出能通过的方法再去实现

2、确定优化做到什么程度才能通过

例题

1、贿赂怪兽

题目描述：开始时你的能力是0，你的目标是从1号怪兽开始，通过所有的n只怪兽如果你当前的能力小于i号怪兽的能力，则必须付出b[i]的钱贿赂这个怪兽然后怪兽就会加入你，他的能力a[i]直接累加到你的能力上如果你当前的能力大于等于i号怪兽的能力，你可以选择直接通过，且能力不会下降但你依然可以选择贿赂这个怪兽，然后怪兽的能力直接累加到你的能力上返回通过所有的怪兽，需要花的最小钱数进行如下的思考: 根据不同的数据量情况设定不同的dp定义假设a[i]数值的范围很大，但是b[i]数值的范围不大，该怎么做？假设a[i]数值的范围不大，但是b[i]数值的范围很大，又该怎么做？

代码如下

 package main.java.class087;  
 import java.io.*;  
 /**  
  * @program: ZuoChengxunAlgorithmClass  
  * @ClassName Code01_BuyMonster  
  * @description: 贿赂怪兽  
  * // 开始时你的能力是0，你的目标是从0号怪兽开始，通过所有的n只怪兽  
  * // 如果你当前的能力小于i号怪兽的能力，则必须付出b[i]的钱贿赂这个怪兽  
  * // 然后怪兽就会加入你，他的能力a[i]直接累加到你的能力上  
  * // 如果你当前的能力大于等于i号怪兽的能力，你可以选择直接通过，且能力不会下降  
  * // 但你依然可以选择贿赂这个怪兽，然后怪兽的能力直接累加到你的能力上  
  * // 返回通过所有的怪兽，需要花的最小钱数  
  * // 测试链接 : https://www.nowcoder.com/practice/736e12861f9746ab8ae064d4aae2d5a9  
  * @author: zs宝  
  * @create: 2025-10-18 10:32  
  * @Version 1.0  
  **/public class Code01_BuyMonster {  
     public static void main(String[] args) throws IOException {  
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
         StreamTokenizer in = new StreamTokenizer(br);  
         PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));  
         while (in.nextToken() != StreamTokenizer.TT_EOF) {  
             int n = (int) in.nval;  
             int[] a = new int[n + 1];  
             int[] b = new int[n + 1];  
             for (int i = 1; i <= n; i++) {  
                 in.nextToken();  
                 a[i] = (int) in.nval;  
                 in.nextToken();  
                 b[i] = (int) in.nval;  
             }  
             out.println(compute1(n, a, b));  
         }  
         out.flush();  
         out.close();  
         br.close();  
     }  
   
     /**  
      * 假设 假设a[i]数值的范围很大，但是b[i]数值的范围不大，改如何定义dp数组进行求解  
      * @param n  
      * @param a:怪兽可以带来的能力值  
      * @param b：贿赂怪兽所要的金额  
      * @return  
      */  
     public static int compute1(int n,int[]a,int[]b){  
         int m=0;  
         for(int money:b){  
             m+=money;  
         }  
         //dp[i][j]:通过1-i只怪兽，在贿赂金额不超过b的情况下，获得的最大能力是多少  
         int[][]dp=new int[n+1][m+1];  
         //严格按照位置依赖的动态规划  
         for(int i=1;i<=n;i++){  
             for(int j=0;j<=m;j++){  
                 dp[i][j]=Integer.MIN_VALUE;  
                 //如果上一次获得的能力足够，不贿赂怪兽  
                 if(dp[i-1][j]>=a[i]){  
                     dp[i][j]=dp[i-1][j];  
                 }  
                 //不管上一次获得的能力够不够，都贿赂怪兽  
                 if(j-b[i]>=0 && dp[i-1][j-b[i]]!=Integer.MIN_VALUE){  
                     dp[i][j]=Math.max(dp[i][j],dp[i-1][j-b[i]]+a[i]);  
                 }  
             }  
         }  
         int ans=-1;  
         for(int j=0;j<=m;j++){  
             if(dp[n][j]!=Integer.MIN_VALUE){  
                 ans=j;  
                 break;  
             }  
         }  
         return ans;  
     }  
   
     /**  
      * 假设 假设b[i]数值的范围很大，但是a[i]数值的范围不大，改如何定义dp数组进行求解  
      * @param n  
      * @param a:怪兽可以带来的能力值  
      * @param b：贿赂怪兽所要的金额  
      * @return  
      */  
     public static int compute3(int n, int[] a, int[] b) {  
         int m=0;  
         for(int power:a){  
             m+=power;  
         }  
         //dp[i][j]:在能力为j的情况下，通过1-i只怪兽，所花费的最小贿赂金额  
         int[][]dp=new int[n+1][m+1];  
         //由于是能力为j的情况，当没有怪兽是，能力只会为0，要想有能力，需要的金额是无限的  
         for(int j=1;j<=m;j++){  
             dp[0][j]=Integer.MAX_VALUE;  
         }  
         for(int i=1;i<=n;i++){  
             for(int j=0;j<=m;j++){  
                 dp[i][j]=Integer.MAX_VALUE;  
                 //不用贿赂的情况  
                 if(j>=a[i] && dp[i-1][j]!=Integer.MAX_VALUE){  
                     dp[i][j]=dp[i-1][j];  
                 }  
                 //贿赂的情况  
                 if(j>=a[i] && dp[i-1][j-a[i]]!=Integer.MAX_VALUE){  
                     dp[i][j]=Math.min(dp[i][j],dp[i-1][j-a[i]]+b[i]);  
                 }  
             }  
         }  
         int ans=Integer.MAX_VALUE;  
         for(int j=0;j<=m;j++){  
             ans=Math.min(ans,dp[n][j]);  
         }  
         return ans==Integer.MAX_VALUE?-1:ans;  
     }  
   
 }

2、选择k个数字使得两集合累加和相差不超过1

题目描述：给定一个正数n，表示1~n这些数字都可以选择给定一个正数k，表示要从1~n中选择k个数字组成集合A，剩下数字组成集合B 希望做到集合A和集合B的累加和相差不超过1 如果能做到，返回集合A选择了哪些数字，任何一种方案都可以如果不能做到，返回长度为0的数组 2 <= n <= 10^6 1 <= k <= n 来自真实大厂笔试，没有测试链接，用对数器验证

评估一下数据规模，01背包的解法可行吗？

解题思路：

首先我们来看下01背包的思路到底行不行
- 要将一个数组分成两个集合，假设两个集合的累加和分别为A, B，数组总的累加和为sum
- 那么有A+B=sum，现在想要 |A-B|<=1, 假设A>=B, 有A-B+A+B<=1+A+B，则2A<=1+sum
- 假设sum为偶数，那么A=sum/2, B=sum/2
- 假设sum为奇数，那么A=sum/2+1, B=sum/2
- 那么01背包进行选择的目标就出来了
- 每次对于一个数值，选还是不选，同时要统计当前的累加和是多少，当前选了几个数
- 于是dp数组的规模就有 dp[n][k][sum], 已知2 <= n <= 10^6，1 <= k <= n
- 其dp数组的规模必然超过10^7, 于是01背包的解法思路，在这里面临最大数据量的时候，一定过不了
当一个题动态规划暴力递归过不了的时候，这个题一定有其它方法运题目内部其特有的规律去大量减少运算
这里我们换个思路，要想能在数组中找到K个数满足要求，那么这个K个数的累加和sum应该在最小的K个数和最大的K个数的范围之内，才算是有解
- 若在范围内，那么我们可以求解出最小的K个数的累和minSum, 与要求的目标sum的的差值need。
- 而这个K个最小sum的移动增大范围为n-k, 那么可以通过need与n-k求解出需要几个数值增加n-k.
- 若need%（n-k）!=0, 说明还有一个数值需要增加need%（n-k）个距离
- 最小K个数中的剩余值，不变，则找到一种组合方式

代码如下

 package main.java.class087;  
   
 /**  
  * @program: ZuoChengxunAlgorithmClass  
  * @ClassName Code02_PickNumbersClosedSum  
  * @description: 选择k个数字使得两集合累加和相差不超过1  
  * // 给定一个正数n，表示1~n这些数字都可以选择  
  * // 给定一个正数k，表示要从1~n中选择k个数字组成集合A，剩下数字组成集合B  
  * // 希望做到集合A和集合B的累加和相差不超过1  
  * // 如果能做到，返回集合A选择了哪些数字，任何一种方案都可以  
  * // 如果不能做到，返回长度为0的数组  
  * // 2 <= n <= 10^6  
  * // 1 <= k <= n * // 来自真实大厂笔试，没有测试链接，用对数器验证  
  * @author: zs宝  
  * @create: 2025-10-18 11:27  
  * @Version 1.0  
  **/public class Code02_PickNumbersClosedSum {  
     // 正式方法  
     // 最优解  
     public static int[] pick(int n, int k) {  
         //计算数组的累加和  
         long sum=(n+1)*n/2;  
         //当寻找的累加和是sum/2时  
         int[]ans=generate(n,k,sum/2);  
         //若找不到，则在累加和为奇数时，试试寻找sum/2+1  
         if(ans.length==0 && (sum &1)==1){  
             ans=generate(n,k,sum/2+1);  
         }  
         return ans;  
     }  
   
     /**  
      * 在1-n个数间寻找K个数，使得累加和为sum  
      * @param n  
      * @param k  
      * @param sum  
      * @return  
      */  
     public static int[]generate(int n,int k,long sum){  
         //计算最小的K个数的累积和  
         long minSum=(k+1)*k/2;  
         //计算最大的K个数的累加和  
         int range=n-k;  
         long maxSum=minSum+(long)range*k;  
         //若要求的sum值在minSum-maxSum之外，则无法寻找K个数满足要求  
         if(sum< minSum || sum>maxSum){  
             return new int[0];  
         }  
         //接下来就是能够找到k个数满足要求时  
         //还需要多少的和满足要求  
         long need=sum-minSum;  
         //需要K中需要最后面几个数挪动range个位置  
         int rightSize=(int)(need/range);  
         //判断挪动rightSize个数后，是否还有需要挪动的不是range的值  
         int midIndex=k-rightSize+(int)(need%range);  
         //原K个小数中还剩下几个数保持不动  
         int leftIndex=k-rightSize-(need%range==0?0:1);  
         //放入结果集中去  
         int[]ans=new int[k];  
         for(int i=0;i<leftIndex;i++){  
             ans[i]=i+1;  
         }  
         if(need%range!=0){  
             ans[leftIndex]=midIndex;  
         }  
         for(int j=0,i=k-1;j<rightSize;i--,j++){  
             ans[i]=n-j;  
         }  
         return ans;  
     }  
     // 为了验证  
     // 检验得到的结果是否正确  
     public static boolean pass(int n, int k, int[] ans) {  
         if (ans.length == 0) {  
             if (canSplit(n, k)) {  
                 return false;  
             } else {  
                 return true;  
             }  
         } else {  
             if (ans.length != k) {  
                 return false;  
             }  
             int sum = (n + 1) * n / 2;  
             int pickSum = 0;  
             for (int num : ans) {  
                 pickSum += num;  
             }  
             return Math.abs(pickSum - (sum - pickSum)) <= 1;  
         }  
     }  
   
     // 记忆化搜索  
     // 不是最优解，只是为了验证  
     // 返回能不能做到  
     public static boolean canSplit(int n, int k) {  
         int sum = (n + 1) * n / 2;  
         int wantSum = (sum / 2) + ((sum & 1) == 0 ? 0 : 1);  
         int[][][] dp = new int[n + 1][k + 1][wantSum + 1];  
         return f(n, 1, k, wantSum, dp);  
     }  
   
     public static boolean f(int n, int i, int k, int s, int[][][] dp) {  
         if (k < 0 || s < 0) {  
             return false;  
         }  
         if (i == n + 1) {  
             return k == 0 && s == 0;  
         }  
         if (dp[i][k][s] != 0) {  
             return dp[i][k][s] == 1;  
         }  
         boolean ans = f(n, i + 1, k, s, dp) || f(n, i + 1, k - 1, s - i, dp);  
         dp[i][k][s] = ans ? 1 : -1;  
         return ans;  
     }  
   
     // 为了验证  
     // 对数器  
     public static void main(String[] args) {  
         int N = 60;  
         int testTime = 5000;  
         System.out.println("测试开始");  
         for (int i = 0; i < testTime; i++) {  
             int n = (int) (Math.random() * N) + 2;  
             int k = (int) (Math.random() * n) + 1;  
             int[] ans = pick(n, k);  
             if (!pass(n, k, ans)) {  
                 System.out.println("出错了!");  
             }  
         }  
         System.out.println("测试结束");  
     }  
 }

3、两个排列的最长公共子序列长度

题目描述：给出 1,2,…,n 的两个排列 P1 和 P2 ，求它们的最长公共子序列。输入格式：第一行是一个数 n。接下来两行，每行为 n 个数，为自然数 1,2,…,n 的一个排列。输出格式：一个数，即最长公共子序列的长度。输入输出样例 输入 #1 5 3 2 1 4 5 1 2 3 4 5 输出 #1 3 说明/提示

对于 50% 的数据， n≤10^3；
对于 100% 的数据， n≤10^5。

解题思路：

最长公共子序列问题，我们在之前的 067、从递归入手二维动态规划中有过类似的题，解法为
- 两个字符串从后往前看，每次判断当前两字符串索引位置的字符是否相等，若相等则为索引位置-1 的最长公共子序列+1，不等则取两个索引位置的其中一个 -1 另外一个不变的最大值；然后根据这个递归转为动态规划，二维，分别以两个字符串长度为二维边界，根据递归则 dp[ i ] [ j ]与其上，左，左上位置的数值有关
这里我们看数据量在1-10^5, 如果建立dp表，dp表的大小会达到10^5* 10⁵⁼¹⁰10这个量级，已经远远超过了10^7这个界限。
于是这个题，普通的最长公共子序列尝试思路是行不通的。
但是这个题给的序列全部都是数字，且两个序列拥有的数字是相同的，将其转化一下
- 那么我们可以记录下其中一个序列的每个数字的位置
- 然后在第二个序列中数字的顺序用一个新数组，存储按照第二个序列数字顺序放置第一个序列中每个数字的位置索引
- 例如
  - 3 2 1 4 5，分别对应索引为0 1 2 3 4
  - 那么另外一个序列 1 2 3 4 5，第一个序列每个数字的索引将成 2 1 0 3 4的次序排列
所以问题就可以转化成次序排列的最长递增子序列问题。

代码如下

 package main.java.class087;  
 import java.io.*;  
 /**  
  * @program: ZuoChengxunAlgorithmClass  
  * @ClassName Code03_PermutationLCS  
  * @description: 两个排列的最长公共子序列长度  
  * // 给出由1~n这些数字组成的两个排列  
  * // 求它们的最长公共子序列长度  
  * // n <= 10^5  
  * // 测试链接 : https://www.luogu.com.cn/problem/P1439  
  * @author: zs宝  
  * @create: 2025-10-20 10:19  
  * @Version 1.0  
  **/public class Code03_PermutationLCS {  
     public static int MAXN = 100001;  
   
     public static int[] a = new int[MAXN];  
   
     public static int[] b = new int[MAXN];  
   
     public static int[] where = new int[MAXN];  
   
     public static int[] ends = new int[MAXN];  
   
     public static int n;  
   
     public static void main(String[] args) throws IOException {  
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
         StreamTokenizer in = new StreamTokenizer(br);  
         PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));  
         while (in.nextToken() != StreamTokenizer.TT_EOF) {  
             n = (int) in.nval;  
             for (int i = 0; i < n; i++) {  
                 in.nextToken();  
                 a[i] = (int) in.nval;  
             }  
             for (int i = 0; i < n; i++) {  
                 in.nextToken();  
                 b[i] = (int) in.nval;  
             }  
             out.println(compute());  
         }  
         out.flush();  
         out.close();  
         br.close();  
     }  
   
     public static int compute(){  
         //求解一个序列中每个数字对应的索引位置  
         for(int i=0;i<n;i++){  
             where[a[i]]=i;  
         }  
         //存储这个索引位置在另外一个序列中将会怎么排列  
         int idxs[]=new int[n];  
         for(int i=0;i<n;i++){  
             idxs[i]=where[b[i]];  
         }  
         //最后求解idxs中的最长递增子序列  
         //标准的最长递增子序列模版  
         return lis(idxs);  
     }  
   
     //标准的最长递增子序列模版  
     public static int lis(int[] idxs){  
         int len=0;  
         for(int i=0,find;i<n;i++){  
             find=bs(len,idxs[i]);  
             if(find==-1){  
                 ends[len++]=idxs[i];  
             }else{  
                 ends[find]=idxs[i];  
             }  
         }  
         return len;  
     }  
   
     /**  
      * 二分查找，寻找>=num的最左位置  
      * @param len  
      * @param num  
      * @return  
      */  
     public static int bs(int len,int num){  
         int l=0;  
         int r=len-1;  
         int m;  
         int ans=-1;  
         while(l<=r){  
             m=(l+r)/2;  
             if(ends[m]>=num){  
                 r=m-1;  
                 ans=m;  
             }else{  
                 l=m+1;  
             }  
         }  
         return ans;  
     }  
   
 }

4、使数组严格递增的最小操作数

题目描述：给你两个整数数组 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

解题思路：

评估一下数据规模，用数组中的值做可变参数可行吗？
dp[i]:从第i位开始，1_{i-1之前的数值已经升序，要想保持升序，i}n至少需要多少次int操作

项目名称	内容填写（每道题一行填写）
📘 题目编号 / 标题	LeetCode 1187 + 使数组严格递增
🧠 题目关键词（原文关键词）	返回使 `arr1` 严格递增所需要的最小「操作」数（可能为 0）。
🧩 抽象问题类型（题目本质）	最小递增模型
🔍 数据规模 / 限制	- `1 <= arr1.length, arr2.length <= 2000` - `0 <= arr1[i], arr2[i] <= 10^9`
🧭 我的初步思路	暴力递归
✅ 正确解法类型	动态规划
❗ 没想到的原因	想不出来如何定义dp，如何递归
📦 归入的题型分类	动态规划类
🧠 触发词（以后遇到就联想）	没思绪
🧪 解法一句话总结	`dp[i]定义`

代码如下

 package main.java.class087;  
   
 import java.util.Arrays;  
   
 /**  
  * @program: ZuoChengxunAlgorithmClass  
  * @ClassName Code04_MakeArrayStrictlyIncreasing  
  * @description: 使数组严格递增的最小操作数  
  * // 给你两个整数数组 arr1 和 arr2  
  * // 返回使 arr1 严格递增所需要的最小操作数（可能为0）  
  * // 每一步操作中，你可以分别从 arr1 和 arr2 中各选出一个索引  
  * // 分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length  
  * // 然后进行赋值运算 arr1[i] = arr2[j]  
  * // 如果无法让 arr1 严格递增，请返回-1  
  * // 1 <= arr1.length, arr2.length <= 2000 * // 0 <= arr1[i], arr2[i] <= 10^9 * // 测试链接 : https://leetcode.cn/problems/make-array-strictly-increasing/  
  * @author: zs宝  
  * @create: 2025-10-20 11:03  
  * @Version 1.0  
  **/public class Code04_MakeArrayStrictlyIncreasing {  
     class Solution {  
         public int makeArrayIncreasing(int[] arr1, int[] arr2) {  
             return makeArrayIncreasing2(arr1, arr2);  
         }  
   
         public int makeArrayIncreasing1(int[] arr1, int[] arr2) {  
             //先将arr2进行排序  
             Arrays.sort(arr2);  
             int m = 1;  
             //对arr2进行去重操作，因为哪怕交换数字，一个数值也只能用一次  
             for (int i = 1; i < arr2.length; i++) {  
                 if (arr2[i] != arr2[m - 1]) {  
                     arr2[m++] = arr2[i];  
                 }  
             }  
             int n = arr1.length;  
             //dp[i]:从第i位开始，1~i-1之前的数值已经升序，要想保持升序，i~n至少需要多少次int操作  
             int[] dp = new int[n];  
             Arrays.fill(dp, -1);  
             int ans = f1(arr1, arr2, n, m, 0, dp);  
             return ans == Integer.MAX_VALUE ? -1 : ans;  
         }  
   
         /**  
          1~i-1已经是一个升序的状态，且i-1位置的数必定是没有操作过的，是arr1种原本的数  
          现在从 i开始一直到n，保持升序，至少需要多少次操作  
          // arr1长度为n，arr2有效部分长度为m  
          // arr2有效部分可以替换arr1中的数字  
          // arr1[0..i-1]已经严格递增且arr1[i-1]一定没有替换  
          // 返回让arr1整体都严格递增，arr1[i...]范围上还需要几次替换  
          // 如果做不到，返回无穷大  
          */  
         public int f1(int[] arr1, int[] arr2, int n, int m, int i, int[] dp) {  
             if (i == n) {  
                 return 0;  
             }  
             if (dp[i] != -1) {  
                 return dp[i];  
             }  
             int ans = Integer.MAX_VALUE;  
             //i位置之前一个位置的数值  
             int pre = i == 0 ? Integer.MIN_VALUE : arr1[i - 1];  
             //在arr2数组中的1-m位置寻找到大于pre的第一个数值位置  
             int find = bs(arr2, m, pre);  
             //接下来开始遍历，枚举哪一个点作为下一次的不操作的点j,i-1~j位置的点则需要操作才行，那么让i-n升序的最小操作次数  
             //即枚举arr1[i...]范围上，第一个不需要替换的位置j  
             for (int j = i, k = 0, next; j <= n; j++, k++) {  
                 //为什么j==n,因为有可能后续的点都需要进行替换操作  
                 if (j == n) {  
                     ans = Math.min(ans, k);  
                 } else {  
                     //当前点若不需要操作，至少满足一个大于pre的条件  
                     if (pre < arr1[j]) {  
                         next = f1(arr1, arr2, n, m, j + 1, dp);  
                         if (next != Integer.MAX_VALUE) {  
                             ans = Math.min(ans, k + next);  
                         }  
                     }  
                     //若当前点需要操作，这意味着不操作的点在后面位置，则  
                     if (find != -1 && find < m) {  
                         //此时pre意味着枚举不操作点前面的一个数的数值  
                         pre = arr2[find++];  
                     } else {  
                         break;  
                     }  
                 }  
             }  
             dp[i] = ans;  
             return ans;  
         }  
   
         public int bs(int[] arr, int len, int num) {  
             int l = 0;  
             int r = len - 1;  
             int m;  
             int ans = -1;  
             while (l <= r) {  
                 m = (l + r) / 2;  
                 if (arr[m] > num) {  
                     r = m - 1;  
                     ans = m;  
                 } else {  
                     l = m + 1;  
                 }  
             }  
             return ans;  
         }  
 
         //严格按照位置依赖的动态规划
         public int makeArrayIncreasing2(int[] arr1, int[] arr2) {  
             //先将arr2进行排序  
             Arrays.sort(arr2);  
             int m = 1;  
             //对arr2进行去重操作，因为哪怕交换数字，一个数值也只能用一次  
             for (int i = 1; i < arr2.length; i++) {  
                 if (arr2[i] != arr2[m - 1]) {  
                     arr2[m++] = arr2[i];  
                 }  
             }  
             int n = arr1.length;  
             //dp[i]:从第i位开始，1~i-1之前的数值已经升序，要想保持升序，i~n至少需要多少次int操作  
             int[] dp = new int[n + 1];  
             Arrays.fill(dp, -1);  
             for (int i = n - 1,ans,pre,find; i >= 0; i--) {  
                 if (i == n) {  
                     return 0;  
                 }  
                 if (dp[i] != -1) {  
                     return dp[i];  
                 }  
                 ans = Integer.MAX_VALUE;  
                 //i位置之前一个位置的数值  
                 pre = i == 0 ? Integer.MIN_VALUE : arr1[i - 1];  
                 //在arr2数组中的1-m位置寻找到大于pre的第一个数值位置  
                 find = bs(arr2, m, pre);  
                 //接下来开始遍历，枚举哪一个点作为下一次的不操作的点j,i-1~j位置的点则需要操作才行，那么让i-n升序的最小操作次数  
                 //即枚举arr1[i...]范围上，第一个不需要替换的位置j  
                 for (int j = i, k = 0, next; j <= n; j++, k++) {  
                     //为什么j==n,因为有可能后续的点都需要进行替换操作  
                     if (j == n) {  
                         ans = Math.min(ans, k);  
                     } else {  
                         //当前点若不需要操作，至少满足一个大于pre的条件  
                         if (pre < arr1[j]) {  
                             next = f1(arr1, arr2, n, m, j + 1, dp);  
                             if (next != Integer.MAX_VALUE) {  
                                 ans = Math.min(ans, k + next);  
                             }  
                         }  
                         //若当前点需要操作，这意味着不操作的点在后面位置，则  
                         if (find != -1 && find < m) {  
                             //此时pre意味着枚举不操作点前面的一个数的数值  
                             pre = arr2[find++];  
                         } else {  
                             break;  
                         }  
                     }  
                 }  
                 dp[i] = ans;  
             }  
             return dp[0]==Integer.MAX_VALUE?-1:dp[0];  
         }  
     }  
 }

参考资料

左程云算法-算法通过系列-087

如果觉得文章对你有用，请随意赞赏

算法动态规划

动态规划22：根据数据量猜解法的技巧

https://zshunbao.top/archives/dong-tai-gui-hua-22-gen-ju-shu-ju-liang-cai-jie-fa-de-ji-qiao

作者

zs宝

发布于

2025-10-20

更新于

2025-10-20

许可协议

CC BY 4.0