DP 线性 - wenzhoullq/leetcode GitHub Wiki

//只针对max(nums[]) <= 1e6的,通过枚举不同的点,这种最简单
//对于枚举的点能否重复,也是有说法的,需要自行判断
        List<int[]>[] list = new List[n+1];
        Arrays.setAll(list,e->new ArrayList<>());
        for(List<Integer> offer : offers){
            list[offer.get(1)].add(new int[]{offer.get(0),offer.get(2)});
        }
        int[] dp = new int[n+1];
        for(int i = 0 ; i < n;i++){
           if(i > 0) dp[i] = dp[i-1];// dp[i+1] = dp[i]
            for(int[] arr:list[i]){
                dp[i] = Math.max(dp[i],dp[arr[0]]+arr[1]);// dp[i+1] = Math.max(dp[i+1],dp[arr[0]]+arr[1]);
            } 
        }
        return dp[n];

// 如果max(nums[]) == 1e9,不能通过枚举点,只能通过枚举段,按结束然后二分查找最满足的段
// 需要注意的细节是一个是二分的left = -1,另一个是枚举事件,要保留事件0,dp的事件是从1开始,但是存在事件0,不然会出现重复的累加
    int[][] arr;
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        this.arr = new int[n][3];
        for(int i = 0; i < n; i++){
            arr[i][0] = startTime[i];
            arr[i][1] = endTime[i];
            arr[i][2] = profit[i];
        }
        Arrays.sort(arr,(a,b)->a[1] - b[1]);
        int[] dp = new int[n+1];
        int ans = 0;
        for(int i = 0 ; i < n ;i++){
            int f = find(i,arr[i][0]);
            dp[i+1] = Math.max(dp[i],dp[f+1] +arr[i][2]);
        }
        return dp[n];
    }
    int find(int i,int t){
        int left = -1, right = i;
        while(left < right){
            int mid = (left+right+1)/2;
            if(arr[mid][1] <= t) left = mid;
            else right = mid -1;
        }
        return left;
    }