有一段时间没做题了,前几天打开做了几道,其中有一道DP。
从一开始的思路错误,到后面优化。因为整个过程花了一些时间,所以想把这个过程记录一下。
原题
来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/ma…
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
为了方便看,把原题贴出来如下⬇️
初步思考
打开题,瞅了瞅,求最大报酬?那肯定用动态规划了。说起来这道题是不是在哪里见过。刚打开题就一直想状态转移方程,想DP数组。(温馨提示:以下内容为初步思考过程,想看正确的思路可跳过这部分)
有了,我用一个二维数组slice[][]
,用 slice[i][j]
表示从时间 i~j
可以获得的最大收益,这样结果就是slice[minStartTime][maxEndTime]
。(因为我用Go,用切片表示,下文的数组在Go里用切片表示)
思路确定后,开始思考状态转移方程,填充二维数组。
在每段时间线内挑选工作,遍历工作列表,如果该工作在时间线内,表明该工作可选,计算最大收益。
// 第k项工作
if startTime[k] >= i && endTime <= j {
// 分情况
if startTime[k] > i && endTime[k] < j {
// 工作在中间时间段
// 最大收益=max(原来的最大收益, profit[k]+左边时间段的最大收益处+右边时间段的最大收益)
slice[i][j] = max(slice[i][j],
profit[k] + slice[i][startTime[k]] + slcie[endTime[k]][j])
} else if startTime[k] > i {
// 工作在i时间点之后开始,且j刚好结束(endTime[k] == j)
slice[i][j] = max(slice[i][j],
profit[k] + slice[i][startTime[k]])
} else if endTime[k] < j {
// 工作刚好在i开始,且在j之前结束
slice[i][j] = max(slice[i][j],
profit[k] + slice[endTime[k]][j])
} else {
// 工作刚好在i开始,且刚好在j结束
slice[i][j] = max(slice[i][j], profit[k])
}
}
思路理清了,coding
func jobScheduling(startTime []int, endTime []int, profit []int) int {
// 工作数量
n := len(startTime)
minTime := math.MaxInt32
maxTime := -1
for i := 0; i < n; i++ {
if startTime[i] < minTime {
minTime = startTime[i]
}
if endTime[i] > maxTime {
maxTime = endTime[i]
}
}
// slice[i][j] 表示 i~j 时间段所能获得的最大收益
slice := make([][]int, maxTime+2)
for i := minTime; i < maxTime+1; i++ {
slice[i] = make([]int, maxTime+2)
}
for i := maxTime+1; i >= minTime; i-- {
for j := i+1; j <= maxTime; j++ {
// 挑选工作
for k := 0; k < n; k++ {
// 工作在时间段内
if startTime[k] >= i && endTime[k] <= j {
if startTime[k] > i && endTime[k] < j {
slice[i][j] = max(slice[i][j], slice[i][startTime[k]] + profit[k] + slice[endTime[k]][j])
} else if startTime[k] > i {
slice[i][j] = max(slice[i][j], slice[i][startTime[k]] + profit[k])
} else if endTime[k] < j {
slice[i][j] = max(slice[i][j], profit[k] + slice[endTime[k]][j])
} else {
slice[i][j] = max(slice[i][j], profit[k])
}
}
}
}
}
return slice[minTime][maxTime]
}
func max(x, y int) int {
if x > y {
return x
} else {
return y
}
}
想必有大佬已经看出来有多愚蠢了,是的我根本没看提示里的取值范围。空间理所当然爆了23333,时间也得来到3次方,只过了十几个test case,打开看详情的时候人懵了,数值几万几万的。望各位大佬不要嘲笑,小弟只是个新手。
后面又开始重新想状态转移方程,也没想到什么好办法(牢记以后得看数值范围,且不要急着想DP数组)。
暴力
确实一直死磕想状态转移也想不出什么了。算了,先用暴力写写看吧(暴力大概是我们普通人的最爱吧)。
大致思路: 把所有可选的情况整理出来,再选择收益最高的情况。
因为是在一条时间线上工作,交叉的部分不能再选。先按开始时间排一下序。
// 既然是暴力,排序不是核心,就先随便排排
n := len(startTime)
for i := 0; i < n; i++ {
idx := i
for j := i+1; j < n; j++ {
if startTime[j] < startTime[idx] {
idx = j
}
}
// 结束时间,对应利润也要相应的交换
startTime[i], startTime[idx] = startTime[idx], startTime[i]
endTime[i], endTime[idx] = endTime[idx], endTime[i]
profit[i], profit[idx] = profit[idx], profit[i]
}
排完序之后,工作的时间线就变成了第一项的开始时间,到最后一项的结束时间,所以可以用每一项工作的索引去表示时间范围。如果说上一项工作的结束时间比该项的开始时间还大,则需要跳过这一项工作,直接寻找下一项工作。
// 写一个函数,返回 从idx索引的开始时间到整条时间线结束所能获得的最大收益
// maxProfit(0)表示从开始到结束得到最大收益
func maxProfit(idx int) int {
// 索引超过了最大的,表示没有工作了,直接返回收益为0
if idx >= N {
return 0
}
// 计算下一个可选的工作, 即开始时间在本EndTime[idx]之后
i := idx + 1
for ; i < len(StartTime) && StartTime[i] < EndTime[idx]; i++ {}
// 用两个变量表示,选择该项工作了的最大收益,不选该工作的最大收益
// (选与不选,背包???emmm有内味了)
var p1, p2 int
// 选择该工作收益
p1 = Profit[idx] + maxProfit(i)
// 不选该工作,将时间段空出来给其他工作,索引项直接从该项的下一项开始
p2 = maxProfit(idx+1)
if p1 > p2 {
return p1
} else {
return p2
}
}
因为是暴力法,理所当然是会超时的, 只过了几个test case,完整的代码就不贴出来了。
但一番思考过后,相信大家都能看出一点端倪了(最喜欢 选与不选 这个词了)。
记忆化
其实已经比较明显了,每一次执行maxProfit(idx)
都有可能重复计算,即所谓的重叠子问题,到这里可以重新思考状态转移方程了。但这一步我们先采用记忆化的方法(自顶向下动态规划?)。
我们引入一个 memory[]
数组,用来存放 maxProfit(idx)
的值,在调用 maxProfit
时,如果需要继续向下调用,我们先判断向下调用的idx
是否已经存在 memory[]
中,有的话直接替代,而不是调用函数。
coding
func jobScheduling(startTime []int, endTime []int, profit []int) int {
// 按开始时间排序
// 排序和前面一样,现在不是重点,后面再优化
// 为了方便设置为全局变量
N = len(startTime)
StartTime = startTime
EndTime = endTime
Profit = profit
memory = make([]int, N+1)
// 将各项都初始化为-1表示未存储
for i := 0; i <= N; i++ {
memory[i] = -1
}
return maxProfit(0)
}
var StartTime []int
var EndTime []int
var Profit []int
var memory []int
var N int
func maxProfit(idx int) int {
// 没有工作了
if idx >= N {
return 0
}
// 计算下一个可选的索引
i := idx + 1
for ; i < len(StartTime) && StartTime[i] < EndTime[idx]; i++ {}
var p1, p2 int
// 选择该工作的最高报酬
// 如果memory有保存相应结果,直接使用
if memory[i] != -1 {
p1 = Profit[idx] + memory[i]
} else {
p1 = Profit[idx] + maxProfit(i)
}
// 不选择该工作的最高报酬
if memory[idx+1] != -1 {
p2 = memory[idx+1]
} else {
p2 = maxProfit(idx+1)
}
// 结果保存到memory
if p1 > p2 {
memory[idx] = p1
} else {
memory[idx] = p2
}
return memory[idx]
}
通过记忆化(缓存),减少重复问题的计算,减少函数调用次数。执行一下。
通过了耶,但这个。。。QWQ一言难尽用时。来优化吧。
递归转迭代
通过上一节的改造,已经可以通过所有的test case,接下来就是优化阶段。不过再此之前,再改造一下,把递归改成迭代(就是dp啦)。
用一个数组dp[]
存放收益,dp[i]
表示从startTime[i]
开始到整条时间线结束所能获得的最大收益。填充dp
数组,最后return dp[0]
即可。
状态转移方程dp[i] = max(profit[i]+dp[下一个可选], dp[i+1])
func jobScheduling(startTime []int, endTime []int, profit []int) int {
// 按开始时间排序
// 排序和前面一样,现在不是重点,后面再优化
//预留一个位置,防越界
dp := make([]int, n+1)
for i := n - 1; i >= 0; i-- {
j := i + 1
for ; j < n && startTime[j] < endTime[i]; j++ {}
dp[i] = max(profit[i] + dp[j], dp[i+1])
}
return dp[0]
}
改造成迭代后代码就看起来十分精简了,核心就那么几行(把递归改成迭代并不会减少多少时间,只是减少了递归调用函数保存运行的堆栈空间)。
优化
dp的代码十分精简,虽然内部有嵌套一层循环,但实际上时间复杂度连O(n^2)都不到。可想而之,造成用时过长的原因其实是排序的问题。再次看一下排序的代码。
n := len(startTime)
for i := 0; i < n; i++ {
idx := i
for j := i+1; j < n; j++ {
if startTime[j] < startTime[idx] {
idx = j
}
}
startTime[i], startTime[idx] = startTime[idx], startTime[i]
endTime[i], endTime[idx] = endTime[idx], endTime[i]
profit[i], profit[idx] = profit[idx], profit[i]
}
可以看到每次排序,都需要交换三组数据,要知道交换是比较耗时的,何况是三组。想办法把交换去掉。
// 按开始时间排序
sortIdx := make([]int, n)
used := make([]bool, n)
for i := 1; i < n; i++ {
if startTime[i] < startTime[sortIdx[0]] {
sortIdx[0] = i
}
}
used[sortIdx[0]] = true
for i := 1; i < n; i++ {
min := math.MaxInt32
idx := 0
for j := 0; j < n; j++ {
if startTime[j] <= min && startTime[j] >= startTime[sortIdx[i-1]] && !used[j] {
idx = j
min = startTime[j]
}
}
sortIdx[i] = idx
used[idx] = true
}
用一个sortIdx[]
保存排序后的索引,比如sortIdx[0] = 5
表示开始时间最小的是第六项工作,用一个标记数组used[]
来辅助,这样就去掉了三次交换的工作。之后调整一下下面的代码就好了。
跑一下
少了一半差不多吧,不过还远远不够。
自己再怎么写排序,也比不上内置的排序算法。使用比较器,通过定义自己的比较规则使用内置的排序算法。(说起来为什么不一开始就用呢,就没这么多事了,真是愚昧啊)
定义一个结构体(类?),把每一项工作的开始,结束,收益对应起来。
type Work struct {
start int
end int
profit int
}
type WorkSlice []Work
实现比较接口,定义比较规则。其他语言也是同理,自定义比较器,使用接口等等,具体看相应的文档。
func (ws WorkSlice) Len() int {
return len(ws)
}
func (ws WorkSlice) Less(i, j int) bool {
return ws[i].start < ws[j].start
}
func (ws WorkSlice) Swap(i, j int) {
ws[i], ws[j] = ws[j], ws[i]
}
这样就可以使用内置的sort包调用排序算法了。
完整coding
func jobScheduling(startTime []int, endTime []int, profit []int) int {
n := len(startTime)
ws := make([]Work, n)
// 初始化
for i := 0; i < n; i++ {
ws[i] = Work{startTime[i], endTime[i], profit[i]}
}
// 排序
sort.Sort(WorkSlice(ws))
dp := make([]int, n+1)
for i := n - 1; i >= 0; i-- {
j := i + 1
for ; j < n && ws[j].start < ws[i].end; j++ {}
dp[i] = max(ws[i].profit + dp[j], dp[i+1])
}
return dp[0]
}
type Work struct {
start int
end int
profit int
}
type WorkSlice []Work
func (ws WorkSlice) Len() int {
return len(ws)
}
func (ws WorkSlice) Less(i, j int) bool {
return ws[i].start < ws[j].start
}
func (ws WorkSlice) Swap(i, j int) {
ws[i], ws[j] = ws[j], ws[i]
}
func max(x, y int) int {
if x > y {
return x
} else {
return y
}
}
提交一下,over
To be continue