动态规划之二分查找优化

1235. 规划兼职工作

2008. 出租车的最大盈利

1751. 最多可以参加的会议数目 II

本篇文章总结「动态规划」结合「二分查找」来一波优化！！

规划兼职工作

题目详情可见 规划兼职工作

其实和「背包问题」很像，关于「背包问题」总结可见 经典动态规划：0-1 背包问题

首先定义一下dp[i]：表示对于前i个兼职，可以获得的最大报酬

对于每个兼职，我们可以选择也可以不选择。当处于第i个兼职时，对应的状态转移方程如下：

其中 $j$$j$ 为满足 $endTime[j]\le startTime[i]$$endTime[j] \le startTime[i]$ 的最大值

现在的问题就转化成如何快速找到这个j，先将所有兼职根据endTime递增排序，如下图所示：

在有序序列中快速查找一个值，很明显用二分搜索 🔍

下面给出完整代码：

public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
    int n = startTime.length;
    // 技巧：借助下标排序
    Integer[] idx = IntStream.range(0, n).boxed().toArray(Integer[]::new);
    Arrays.sort(idx, (a, b) -> endTime[a] - endTime[b]);
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        // 在 [l, r] 区间内，查找目标值 target
        int l = 0, r = i - 1, target = startTime[idx[i - 1]];
        while (l < r) {
            int m = l + r + 1 >> 1;
            if (endTime[idx[m - 1]] <= target) l = m;
            else r = m - 1;
        }
        dp[i] = Math.max(dp[i - 1], dp[l] + profit[idx[i - 1]]);
    }
    return dp[n];
}

出租车的最大盈利

题目详情可见 出租车的最大盈利

和上一个题目，一模一样，直接给出完整代码：

public long maxTaxiEarnings(int n, int[][] rides) {
    int rn = rides.length;
    Integer[] idx = IntStream.range(0, rn).boxed().toArray(Integer[]::new);
    Arrays.sort(idx, (a, b) -> rides[a][1] - rides[b][1]);
    long[] dp = new long[rn + 1];
    for (int i = 1; i <= rn; i++) {
        int l = 0, r = i - 1, target = rides[idx[i - 1]][0];
        while (l < r) {
            int m = l + r + 1 >> 1;
            if (rides[idx[m - 1]][1] <= target) l = m;
            else r = m - 1;
        }
        dp[i] = Math.max(dp[i - 1], dp[l] + rides[idx[i - 1]][2] + rides[idx[i - 1]][1] - rides[idx[i - 1]][0]);
    }
    return dp[rn];
}

最多可以参加的会议数目 II

题目详情可见 最多可以参加的会议数目 II

这个题目略微有一点升级！！有一个整数k的限制，表示你能参加的最多会议数目，更像背包问题了！！！

还有一个需要注意的点：不能同时参加一个开始日期与另一个结束日期相同的两个会议，所以 $j$$j$ 为满足 $events[j][1]<events[i][0]$$events[j][1] < events[i][0]$ 的最大值

更新一下dp的定义，这里我们需要使用二维：dp[i][j]表示对于前i个会议，当前最多参与的会议数量为j，可以获得的会议价值最大和

对应的状态转移方程如下：

下面给出完整代码：

public int maxValue(int[][] events, int k) {
    int n = events.length;
    Integer[] idx = IntStream.range(0, n).boxed().toArray(Integer[]::new);
    Arrays.sort(idx, (a, b) -> events[a][1] - events[b][1]);
    int[][] dp = new int[n + 1][k + 1];
    for (int i = 1; i <= n; i++) {
        // 在 [l, r] 区间内，查找目标值 target
        int l = 0, r = i - 1, target = events[idx[i - 1]][0];
        while (l < r) {
            int m = l + r + 1 >> 1;
            if (events[idx[m - 1]][1] < target) l = m;
            else r = m - 1;
        }
        for (int j = 1; j <= k; j++) {
            dp[i][j] = Math.max(dp[i - 1][j], dp[l][j - 1] + events[idx[i - 1]][2]);
        }
    }
    return dp[n][k];
}