LeetCode 1235.规划兼职工作

1,008 阅读9分钟

有一段时间没做题了,前几天打开做了几道,其中有一道DP。

从一开始的思路错误,到后面优化。因为整个过程花了一些时间,所以想把这个过程记录一下。

原题

链接在此 1235. 规划兼职工作

来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/ma…
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

为了方便看,把原题贴出来如下⬇️

img
img

初步思考

打开题,瞅了瞅,求最大报酬?那肯定用动态规划了。说起来这道题是不是在哪里见过。刚打开题就一直想状态转移方程,想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]
}

通过记忆化(缓存),减少重复问题的计算,减少函数调用次数。执行一下。

img

通过了耶,但这个。。。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[]来辅助,这样就去掉了三次交换的工作。之后调整一下下面的代码就好了。

跑一下

img

少了一半差不多吧,不过还远远不够。

自己再怎么写排序,也比不上内置的排序算法。使用比较器,通过定义自己的比较规则使用内置的排序算法。(说起来为什么不一开始就用呢,就没这么多事了,真是愚昧啊)

定义一个结构体(类?),把每一项工作的开始,结束,收益对应起来。

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

img

To be continue