本文的网课内容学习自B站左程云老师的算法详解课程旨在对其中的知识进行整理和分享~网课链接算法讲解083【必备】动态规划中用观察优化枚举的技巧-下_哔哩哔哩_bilibili一.规划兼职工作题目规划兼职工作算法原理整体原理该问题要求在多个时间重叠的兼职工作中选择一组不重叠的工作使得总报酬最大。通过动态规划结合二分查找来高效解决排序处理将所有工作按结束时间升序排序便于后续处理。动态规划dp[i]表示前i个工作能获得的最大报酬。对于每个工作i有两种选择不选该工作dp[i] dp[i-1]选该工作找到不冲突的前一个工作jdp[i] profit[i] dp[j]二分查找优化快速找到不冲突的前一个工作。具体步骤数据预处理将工作信息存入二维数组jobs并按结束时间排序。动态规划初始化dp jobs第一个工作的报酬状态转移遍历每个工作i使用二分查找找到结束时间不超过当前工作开始时间的最后一个工作j。选择当前工作dp[i] profit[i] dp[j]不选择当前工作dp[i] dp[i-1]取两者较大值更新dp[i]结果获取dp[n-1]即为最大报酬复杂度分析时间复杂度O(nlogn)排序O(nlogn)动态规划 二分查找O(nlogn)空间复杂度O(n)存储工作信息O(n)DP数组O(n)示例假设输入startTime [1,2,3,3] endTime [3,4,5,6] profit [50,10,40,70]处理过程排序后工作顺序工作0[1,3,50]工作1[2,4,10]工作2[3,5,40]工作3[3,6,70]DP计算dp 50dp max(10 dp[find(0,2)], dp) max(100,50) 50dp max(40 dp[find(1,3)], dp) max(4050,50) 90dp max(70 dp[find(2,3)], dp) max(7050,90) 120最终结果120优化点二分查找优化快速定位不冲突的前驱工作空间优化可使用滚动数组减少空间复杂度总结该算法通过合理排序和动态规划结合二分查找优化高效解决了工作选择问题适用于类似需要选择不重叠区间获得最大收益的场景。代码实现import java.util.Arrays; // 规划兼职工作 // 你打算利用空闲时间来做兼职工作赚些零花钱这里有n份兼职工作 // 每份工作预计从startTime[i]开始、endTime[i]结束报酬为profit[i] // 返回可以获得的最大报酬 // 注意时间上出现重叠的 2 份工作不能同时进行 // 如果你选择的工作在时间X结束那么你可以立刻进行在时间X开始的下一份工作 // 测试链接 : https://leetcode.cn/problems/maximum-profit-in-job-scheduling/ public class Code01_MaximumProfitInJobScheduling { public static int MAXN 50001; public static int[][] jobs new int[MAXN][3]; public static int[] dp new int[MAXN]; public static int jobScheduling(int[] startTime, int[] endTime, int[] profit) { int n startTime.length; for (int i 0; i n; i) { jobs[i][0] startTime[i]; jobs[i][1] endTime[i]; jobs[i][2] profit[i]; } // 工作按照结束时间从小到大排序 Arrays.sort(jobs, 0, n, (a, b) - a[1] - b[1]); dp[0] jobs[0][2]; for (int i 1, start; i n; i) { start jobs[i][0]; dp[i] jobs[i][2]; if (jobs[0][1] start) { dp[i] dp[find(i - 1, start)]; } dp[i] Math.max(dp[i], dp[i - 1]); } return dp[n - 1]; } // job[0...i]范围上找到结束时间 start最右的下标 public static int find(int i, int start) { int ans 0; int l 0; int r i; int m; while (l r) { m (l r) / 2; if (jobs[m][1] start) { ans m; l m 1; } else { r m - 1; } } return ans; } }二.K个逆序对数组题目K 个逆序对数组算法原理整体原理该问题要求计算由1到n的数字组成的排列中恰好包含k个逆序对的排列数量。通过动态规划结合滑动窗口优化来高效求解动态规划定义dp[i][j]表示使用数字1到i组成恰好j个逆序对的排列数量边界条件dp 1空排列有0个逆序对状态转移将数字i插入到前i-1个数字的排列中插入位置决定新增的逆序对数量插入到末尾新增0个逆序对插入到倒数第p个位置新增p个逆序对转移方程dp[i][j] sum(dp[i-1][j-p]) for p in [0, min(i-1, j)]滑动窗口优化使用窗口累加和避免重复计算维护一个窗口变量window动态更新其值具体步骤初始化创建dp数组初始化dp 1初始化窗口变量window 1动态规划计算遍历数字1到n对于每个逆序对数量j如果i jwindow dp[i-1][j]否则window dp[i-1][j] - dp[i-1][j-i]dp[i][j] window结果返回dp[n][k]即为最终结果复杂度分析时间复杂度O(nk)空间复杂度O(nk)可优化到O(k)示例n3, k1dp 1dp 1, dp 1dp dp dp 2 结果2排列[1,3,2]和[2,1,3]优化点滑动窗口减少重复求和计算空间压缩可优化为滚动数组总结该算法通过动态规划建模和滑动窗口优化高效解决了逆序对计数问题适用于类似需要排列组合计数的场景。代码实现// K个逆序对数组 // 逆序对的定义如下 // 对于数组nums的第i个和第j个元素 // 如果满足0ijnums.length 且 nums[i]nums[j]则为一个逆序对 // 给你两个整数n和k找出所有包含从1到n的数字 // 且恰好拥有k个逆序对的不同的数组的个数 // 由于答案可能很大答案对 1000000007 取模 // 测试链接 : https://leetcode.cn/problems/k-inverse-pairs-array/ public class Code02_KInversePairsArray { // 最普通的动态规划 // 不优化枚举 public static int kInversePairs1(int n, int k) { int mod 1000000007; // dp[i][j] : 1、2、3...i这些数字形成的排列一定要有j个逆序对请问这样的排列有几种 int[][] dp new int[n 1][k 1]; dp[0][0] 1; for (int i 1; i n; i) { dp[i][0] 1; for (int j 1; j k; j) { if (i j) { for (int p 0; p j; p) { dp[i][j] (dp[i][j] dp[i - 1][p]) % mod; } } else { // i j for (int p j - i 1; p j; p) { dp[i][j] (dp[i][j] dp[i - 1][p]) % mod; } } } } return dp[n][k]; } // 根据观察方法1优化枚举 // 最优解 // 其实可以进一步空间压缩 // 有兴趣的同学自己试试吧 public static int kInversePairs2(int n, int k) { int mod 1000000007; int[][] dp new int[n 1][k 1]; dp[0][0] 1; // window : 窗口的累加和 for (int i 1, window; i n; i) { dp[i][0] 1; window 1; for (int j 1; j k; j) { if (i j) { window (window dp[i - 1][j]) % mod; } else { // i j window ((window dp[i - 1][j]) % mod - dp[i - 1][j - i] mod) % mod; } dp[i][j] window; } } return dp[n][k]; } }