序列dp
- 常规的线性dp只是单纯的依赖dp[i-1]，复杂度由状态的维度数确定
- 而序列dp是要根据规则来找前驱，复杂度由状态的维度数和找前驱的复杂度共同决定
规划兼职工作【LC1235】
你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。
给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。
注意，时间上出现重叠的 2 份工作不能同时进行。
如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。
2022/10/22 小垃圾只能写写暴力，第一次看到序列dp的概念，看来还是做的不够多
动态规划+二分查找
参考宫水三叶姐的题解
定义三元组job[i]=(startTime[i],endTime[i],profit[i])
1.确定dp数组（dp table）以及下标的含义
dp[i]:前i份兼职工作可以获得的最大报酬
2.确定递推公式
。如果不选择该工作
dp[i] = dp[i-1];
。如果选择该工作
- 仅选择完成该工作：dp[i] = job[i-1][2]
- 将该工作接在某个工作后面完成：需要在所有满足**job[j][1] <= job[i-1][0]**中选择报酬最大的dp[j+1]
dp[i] = dp[j+1] + job[i-1][2]
dp[i] = Math.max(dp[i-1],dp[j]+job[i-1][2])
3.如何初始化
。dp[0]=0;
。当我们处理到 job[i]时，为了能够「将所有所能拼接在 job[i]前面的 job[j]归结到一边」并且「所能更新 dp[i]的 dp[j]均被计算」，需要对所有的 job[i]进行右端点（结束时间）进行排升序，并按照从小到大的方式处理每个 job[i]。
4.确定遍历顺序
由dp公式可知，按照结束时间从小到大的顺序遍历job
5.举例推导dp数组
- 代码
class Solution { public int jobScheduling(int[] startTime, int[] endTime, int[] profit) { int len = startTime.length; int[][] data = new int[len][3]; for (int i = 0; i < len;i++){ data[i] = new int[]{startTime[i],endTime[i],profit[i]}; } // 根据endTime进行从小到大排序 Arrays.sort(data,new Comparator<int []>(){ public int compare(int[] data1, int[] data2){ return data1[1] - data2[1]; } }); int[] dp = new int[len+1]; dp[0] = 0; for (int i = 1; i <= len; i++){ // 二分 左闭右开 查找结束时间小于等于当前工作开始时间的最大下标 int left = 0; int right = i-1; int target = data[i-1][0]; while (left < right){ int mid = left + (right-left)/2; if (data[mid][1] > target){ right = mid; }else{ left = mid + 1; } } dp[i] = Math.max(dp[i-1],dp[left] + data[i-1][2] ); } return dp[len]; } }
- 复杂度
。时间复杂度：O(nlogn);dp有n个状态需要转移，每次转移需要进行二分
。空间复杂度：O ( n )
动态规划+下标排序
将下标按照结束时间从小到大，开始时间从小到大排序，然后遍历下标，dp数组定义同上
class Solution { public int jobScheduling(int[] startTime, int[] endTime, int[] profit) { int len = profit.length; int[] dp = new int[len]; Integer[] idx = new Integer[len]; Arrays.parallelSetAll(idx, Integer::valueOf); Arrays.sort(idx, (e1, e2) -> { if (endTime[e1] == endTime[e2]) { return startTime[e1] - startTime[e2]; } return endTime[e1] - endTime[e2]; }); dp[0] = profit[idx[0]]; for (int i = 1; i < len; i++) { dp[i] = profit[idx[i]]; for (int j = i - 1; j >= 0; j--) { // 逆序遍历 找到第一个结束时间小于等于当前开始时间的 即为dp[j]+profit[idx[i]]即为考虑当前工作的最大报酬 if (endTime[idx[j]] <= startTime[idx[i]]) { dp[i] += dp[j]; break; } } dp[i] = Math.max(dp[i], dp[i - 1]); } return dp[len - 1]; } }
- 复杂度
。时间复杂度：O ( n 2 )
。空间复杂度：O ( n )
回溯[超出时间限制]
class Solution { int maxProfit = 0; public int jobScheduling(int[] startTime, int[] endTime, int[] profit) { // boolean[] isWorked = new boolean[startTime.length];// 记录该工作是否兼职过 减少重复计算 int len = startTime.length; int[][] data = new int[len][3]; for (int i = 0; i < len;i++){ data[i] = new int[]{startTime[i],endTime[i],profit[i]}; } // 根据startTime进行从小到大排序 Arrays.sort(data,new Comparator<int []>(){ public int compare(int[] data1, int[] data2){ return data1[0] - data2[0]; } }); // 排序 backtracking(-1,0,data); return maxProfit; } public void backtracking(int preIndex,int pro,int[][] data){ int preEndTime = preIndex == -1 ? 0 : data[preIndex][1]; for (int i = preIndex + 1; i < data.length; i++){ if (data[i][0] >= preEndTime){ pro += data[i][2]; maxProfit = Math.max(maxProfit,pro); backtracking(i,pro,data); pro -= data[i][2]; } } } }
