cswork / 模板打开 500 路题单

第 30 站 · 动态规划

分段与调度优化

按结束时间排序 + 二分找上一个兼容任务 O(n log n)

周赛难度分 难度分 1709–难度分 2035· 中位 难度分 1894（6/6 道题有 zerotrac 周赛分）

打开 500 路题单 · 第 30 站 · 6 题
先学
学完去
没有后续站依赖它。
面试频次
面经里还没有对应到这一站的题。

先做这道

LC 983最低票价中等
卡住再看

在稀疏旅行日期上选择覆盖长度不同的票，处理下一未覆盖日期。

要点

  1. 按结束时间排序后，dp[i] = 前 i 个任务的最优值；第 i 个任务要么不选，要么接在最后一个不冲突的任务后面。
  2. 「最后一个不冲突的任务」在结束时间数组里二分查找，整体 O(n log n)。
  3. 「把数组分成 k 段」这类题，状态通常是 dp[段数][结尾位置]，转移时枚举最后一段从哪里开始。

易错点

  • 首尾相接算不算冲突，决定了用 upper_bound 还是 lower_bound。
  • 按开始时间排序、每次贪心选利润最高的，在带权的版本里不成立。
  • 排序时只排了结束时间，开始时间和利润没有跟着一起动。

看动画

一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。

交互演示 · 逐步观察

二分查找 · 每次排除一半

在有序数组中查找 23

换个输入
20
51
82
123
164
235
386
567
当前处理已发现 / 已计算答案
目标
23
left
0
right
7
mid
—

初始搜索区间包含整个有序数组。下方数字是数组下标。

始终成立如果目标存在，它始终位于闭区间 [left, right] 内。

交互演示 · 逐步观察

二维 DP · 填表求最长公共子序列

「ACBD」和「ABCD」的最长公共子序列

换个输入
∅
A
B
C
D
∅
00,0
00,1
00,2
00,3
00,4
A
01,0
·1,1
·1,2
·1,3
·1,4
C
02,0
·2,1
·2,2
·2,3
·2,4
B
03,0
·3,1
·3,2
·3,3
·3,4
D
04,0
·4,1
·4,2
·4,3
·4,4
当前处理已发现 / 已计算答案
LCS 长度
—

dp[i][j] 是「ACBD」前 i 个字符与「ABCD」前 j 个字符的最长公共子序列长度。第 0 行和第 0 列是空串，都为 0。

始终成立按行从左到右填：算 dp[i][j] 时，它依赖的上方、左方、左上方都已算好。

模板

选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 983。

Python
from bisect import bisect_right


def max_profit(start: list[int], end: list[int], profit: list[int]) -> int:
    """Best total profit of non-overlapping jobs; a job may start when another ends."""
    jobs = sorted(zip(end, start, profit))
    ends = [e for e, _, _ in jobs]
    dp = [0] * (len(jobs) + 1)  # dp[i]: best using the first i jobs by end time
    for i, (_, s, p) in enumerate(jobs):
        k = bisect_right(ends, s, 0, i)  # jobs[:k] all end by time s
        dp[i + 1] = max(dp[i], dp[k] + p)  # skip job i, or take it after jobs[:k]
    return dp[-1]
C++
// Best total profit of non-overlapping jobs; a job may start when another ends.
long long maxProfit(const vector<int>& start, const vector<int>& end, const vector<int>& profit) {
    int n = start.size();
    vector<array<int, 3>> jobs(n);  // {end, start, profit}
    for (int i = 0; i < n; i++) jobs[i] = {end[i], start[i], profit[i]};
    sort(jobs.begin(), jobs.end());
    vector<long long> dp(n + 1, 0);  // dp[i]: best using the first i jobs by end time
    for (int i = 0; i < n; i++) {
        auto [e, s, p] = jobs[i];
        // k = number of earlier jobs that end by time s
        int k = upper_bound(jobs.begin(), jobs.begin() + i, s,
                            [](int t, const array<int, 3>& job) { return t < job[0]; }) - jobs.begin();
        dp[i + 1] = max(dp[i], dp[k] + p);  // skip job i, or take it after the first k jobs
    }
    return dp[n];
}
Java
class Solution {
    // Best total profit of non-overlapping jobs; a job may start when another ends.
    long maxProfit(int[] start, int[] end, int[] profit) {
        int n = start.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> Integer.compare(end[a], end[b]));
        long[] dp = new long[n + 1]; // dp[i]: best using the first i jobs by end time
        for (int i = 0; i < n; i++) {
            int job = order[i];
            int lo = 0, hi = i; // k = number of earlier jobs that end by start[job]
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (end[order[mid]] > start[job]) hi = mid;
                else lo = mid + 1;
            }
            dp[i + 1] = Math.max(dp[i], dp[lo] + profit[job]); // skip it, or take it after them
        }
        return dp[n];
    }
}
Go
import "sort"

// maxProfit returns the best total profit of non-overlapping jobs; a job may
// start when another ends.
func maxProfit(start, end, profit []int) int {
	n := len(start)
	order := make([]int, n)
	for i := range order {
		order[i] = i
	}
	sort.Slice(order, func(a, b int) bool { return end[order[a]] < end[order[b]] })
	dp := make([]int, n+1) // dp[i]: best using the first i jobs by end time
	for i, job := range order {
		// k = number of earlier jobs that end by start[job]
		k := sort.Search(i, func(m int) bool { return end[order[m]] > start[job] })
		dp[i+1] = max(dp[i], dp[k]+profit[job]) // skip it, or take it after them
	}
	return dp[n]
}

常见变体

这一站的题还会用到下面 2 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。

按天 DP：通行证覆盖到今天时间 O(最后一天) · 空间 O(最后一天)

时间轴不长、按天决策（买 1/7/30 天的票、按天排课）时，dp[d] 就是「到第 d 天为止的最优」：今天不出门就沿用昨天；出门就枚举最后买的那张票覆盖到今天，从票生效前一天转移过来。LC 983 最低票价；天数很大时改成只在出行日之间跳，用二分找生效日。

Python
def min_ticket_cost(days: list[int], costs: list[int]) -> int:
    """Cheapest 1-, 7- and 30-day passes (prices costs) covering every travel day (LC 983)."""
    travel = set(days)
    last = days[-1]
    dp = [0] * (last + 1)  # dp[d]: cheapest cover of every travel day up to day d
    for d in range(1, last + 1):
        if d not in travel:
            dp[d] = dp[d - 1]  # nothing to cover today
            continue
        dp[d] = min(
            dp[d - 1] + costs[0],
            dp[max(0, d - 7)] + costs[1],  # a 7-day pass ending today covers d-6..d
            dp[max(0, d - 30)] + costs[2],
        )
    return dp[last]
C++
// Cheapest 1-, 7- and 30-day passes (prices costs) covering every travel day (LC 983).
int minTicketCost(const vector<int>& days, const vector<int>& costs) {
    int last = days.back();
    vector<bool> travel(last + 1, false);
    for (int d : days) travel[d] = true;
    vector<int> dp(last + 1, 0);  // dp[d]: cheapest cover of every travel day up to day d
    for (int d = 1; d <= last; d++) {
        if (!travel[d]) {
            dp[d] = dp[d - 1];  // nothing to cover today
            continue;
        }
        dp[d] = min({dp[d - 1] + costs[0],
                     dp[max(0, d - 7)] + costs[1],  // a 7-day pass ending today covers d-6..d
                     dp[max(0, d - 30)] + costs[2]});
    }
    return dp[last];
}
Java
class Solution {
    // Cheapest 1-, 7- and 30-day passes (prices costs) covering every travel day (LC 983).
    int minTicketCost(int[] days, int[] costs) {
        int last = days[days.length - 1];
        boolean[] travel = new boolean[last + 1];
        for (int d : days) travel[d] = true;
        int[] dp = new int[last + 1]; // dp[d]: cheapest cover of every travel day up to day d
        for (int d = 1; d <= last; d++) {
            if (!travel[d]) {
                dp[d] = dp[d - 1]; // nothing to cover today
                continue;
            }
            dp[d] = Math.min(dp[d - 1] + costs[0],
                    Math.min(dp[Math.max(0, d - 7)] + costs[1], // a 7-day pass ending today covers d-6..d
                            dp[Math.max(0, d - 30)] + costs[2]));
        }
        return dp[last];
    }
}
Go
// minTicketCost returns the cheapest 1-, 7- and 30-day passes covering every travel day (LC 983).
func minTicketCost(days, costs []int) int {
	last := days[len(days)-1]
	travel := make([]bool, last+1)
	for _, d := range days {
		travel[d] = true
	}
	dp := make([]int, last+1) // dp[d]: cheapest cover of every travel day up to day d
	for d := 1; d <= last; d++ {
		if !travel[d] {
			dp[d] = dp[d-1] // nothing to cover today
			continue
		}
		dp[d] = min(dp[d-1]+costs[0],
			dp[max(0, d-7)]+costs[1], // a 7-day pass ending today covers d-6..d
			dp[max(0, d-30)]+costs[2])
	}
	return dp[last]
}
从后往前：做这一题就跳过后面几题时间 O(n) · 空间 O(n)

选了第 i 项就要跳过后面若干项（做题耗脑力、任务有冷却）时，从后往前算 dp[i] =「从 i 开始的最好结果」：不选就是 dp[i + 1]，选就是收益加上跳过之后的 dp。倒着推让「跳到哪里」直接是下标。LC 2140 解决智力问题。

Python
def most_points(questions: list[list[int]]) -> int:
    """questions[i] = [points, brainpower]; solving i skips the next brainpower ones (LC 2140)."""
    n = len(questions)
    dp = [0] * (n + 1)  # dp[i]: best from question i on, filled back to front
    for i in range(n - 1, -1, -1):
        points, skip = questions[i]
        dp[i] = max(dp[i + 1], points + dp[min(n, i + skip + 1)])  # pass on i, or solve it and jump
    return dp[0]
C++
// questions[i] = {points, brainpower}; solving i skips the next brainpower ones (LC 2140).
long long mostPoints(const vector<pair<int, int>>& questions) {
    int n = questions.size();
    vector<long long> dp(n + 1, 0);  // dp[i]: best from question i on, filled back to front
    for (int i = n - 1; i >= 0; i--) {
        auto [points, skip] = questions[i];
        dp[i] = max(dp[i + 1], points + dp[min(n, i + skip + 1)]);  // pass on i, or solve it and jump
    }
    return dp[0];
}
Java
class Solution {
    // questions[i] = {points, brainpower}; solving i skips the next brainpower ones (LC 2140).
    long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] dp = new long[n + 1]; // dp[i]: best from question i on, filled back to front
        for (int i = n - 1; i >= 0; i--)
            dp[i] = Math.max(dp[i + 1], questions[i][0] + dp[Math.min(n, i + questions[i][1] + 1)]); // pass on i, or solve it and jump
        return dp[0];
    }
}
Go
// mostPoints: questions[i] = {points, brainpower}; solving i skips the next brainpower ones (LC 2140).
func mostPoints(questions [][2]int) int {
	n := len(questions)
	dp := make([]int, n+1) // dp[i]: best from question i on, filled back to front
	for i := n - 1; i >= 0; i-- {
		points, skip := questions[i][0], questions[i][1]
		dp[i] = max(dp[i+1], points+dp[min(n, i+skip+1)]) // pass on i, or solve it and jump
	}
	return dp[0]
}

为什么对

  1. 按结束时间排序后，第 i 个工作要么不选（dp[i−1]），要么选；选了它，前面只能接结束不晚于它开始的工作，这些工作恰好构成一个前缀，所以转移是 dp[p] + profit。
  2. 「与 i 兼容的工作是一个前缀」依赖按结束时间排序：结束时间单调，所以可以二分找到最后一个结束时间 ≤ start[i] 的位置 p。
  3. 和不带权的区间贪心不同：带权后结束早的工作不一定更好，交换论证失效，所以需要 DP 比较选与不选。

30 秒口述稿

面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。

中文
带权区间调度，我先按结束时间排序，dp[i] 表示前 i 个工作能拿到的最大收益。第 i 个工作要么不选，答案是 dp[i−1]；要么选，就接在最后一个与它不重叠的工作后面。因为结束时间有序，与它兼容的工作正好是一个前缀，可以二分找到边界，所以整体 O(n log n)。带权之后贪心的交换论证不成立，这就是要用 DP 的原因。
English
For weighted interval scheduling I sort by end time and let dp[i] be the best profit using the first i jobs. Job i is either skipped, giving dp[i − 1], or taken after the last job that does not overlap it. Because end times are sorted, the compatible jobs form a prefix, and binary search finds where it ends, so the whole thing is O(n log n). Once jobs carry weights the greedy exchange argument fails, which is why this needs DP.

自评一下

对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。 只存在这台设备上；登录后会合并到你的账号。

对照要点（0/3）
这道题你会了吗？

小测

3 道概念题和复杂度题。答过的题会和 OA 选择题练习一起按间隔回来复习。 去 OA 选择题练习

3 道题
  1. 带权区间调度（选互不重叠的区间使权值和最大）：区间按结束时间排序后，dp[i] = max(dp[i-1], w[i] + dp[p(i)])。p(i) 是什么，整体复杂度是多少？
  2. 给一组会议时间段，最少需要几间会议室？下面哪个说法正确？
  3. jobs 是 n 个 (开始, 结束, 权值)。时间复杂度是？
    from bisect import bisect_right

def best(jobs):
    jobs.sort(key=lambda j: j[1])
    ends = [e for _, e, _ in jobs]
    dp = [0] * (len(jobs) + 1)
    for i, (s, e, w) in enumerate(jobs):
        k = bisect_right(ends, s, 0, i)
        dp[i + 1] = max(dp[i], dp[k] + w)
    return dp[-1]

作答记录只保存在这台设备的浏览器里；登录后打开OA 选择题练习页，会存进账号。

模板练习

用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。

下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。

分档练习

本站在 500 路里的 6 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。

核心 5

#题目一句话思路难度分
983最低票价在稀疏旅行日期上选择覆盖长度不同的票，处理下一未覆盖日期。难度分 1786
2140解决智力问题在跳过和答题后的强制跨越之间选择，训练带偏移的后缀DP。难度分 1709
1235规划兼职工作把带收益的区间选择结合排序、二分和DP，处理首尾相接的兼容工作。难度分 2023
2008出租车的最大盈利将接客收入建模为带权区间，练习距离与小费合成权重及大整数收益。难度分 1872
1043分隔数组以得到最大和枚举最后一段并增量维护段最大值，控制每段长度上限。难度分 1916

进阶 1

#题目一句话思路难度分
1335工作计划的最低难度按天数和前缀长度做分段DP，保证每天至少一个任务并处理无解。难度分 2035

本站 OA 真题 8

全部 8 道