题目分析

又遇到困难题了，心态崩了啊。小伙伴们不要害怕困难题，在面试的时候遇到困难题，不会做是正常的，可以向面试官询问解题思路或者更换题目，虽然不推荐这样做，但是也总比浪费面试时间更好，如果在那里啃半天也没有想出来，基本上是挂了。如果是笔试遇到了困难题，没用思路，可以先跳过这个题目，最后有时间再做。这个题目和前两天遇到的题目有些类似，都是可以回溯求解，但是时间复杂度又很大的题型。遇到这类题，我们首先要去想动态规划

动态规划

共有m个任务，n个工人，最小利润为minProfit。那么本问题具有最优子问题，第m个任务需要的工人数为group[m]，可以获得的利润为profit[m]。如果做第m个任务，那么就是求子问题共有m - 1个任务，n - group[m]个工人，最小利润为minProfit - profit[m]的解，如果不做第m个任务，就是求子问题共有m - 1个任务，n个工人，最小利润为minProfit的解。将两个解相加即可。

我们使用dp[i][j][k]代表本问题的解，i代表前i个任务，j代表有j个工人，k代表最小利润为k。有如下关系
$$dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - group[i]][k - profit[i]]$$
因为最小利润为0，因此使用max(0, k - profit[i])代替k - profit[i]。

在状态转移方程中，第i层状态仅与第i - 1层有关，可以使用二维dp进行求解。

值得注意的是动态规划的初始状态，当最小利润为0时，使用0个工人是一种解决方案。如果j表示已经使用j个工人，那么dp[0][0] = 1。但是最终求的结果，要从使用0个工人dp[0][minProfit]累积求和到使用n个工人dp[n][minProfit]。如果j表示可以使用j个工人，那么对于所有的dp[j][0] = 1，因为可以使用j个工人都包括使用0个工人。最终求的结果直接返回dp[n][profit]即可。在Python语言的题解中，j代表已经使用j个工人，在Kotlin语言的题解中，j代表可以使用j个工人，小伙伴们认真理解这句话的涵义。

算法的**时间复杂度为$O(mn \cdot minProfit)$，空间复杂度为$O(n \cdot minProfit)$**。

下面是Python语言的题解

class Solution:
    def profitableSchemes(self, n, minProfit, group, profit) -> int:
        mod = 10 ** 9 + 7
        dp = [[0 for _ in range(minProfit + 1)] for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(len(group)):
            for j in range(n, group[i] - 1, -1):
                for k in range(minProfit, -1, -1):
                    dp[j][k] = (dp[j][k] + dp[j - group[i]][max(0, k - profit[i])]) % mod
        return sum(dp[j][-1] for j in range(n + 1)) % mod

下面是Kotlin语言的题解

class Solution {
    fun profitableSchemes(n: Int, minProfit: Int, group: IntArray, profit: IntArray): Int {
        val mod = (1e9 + 7).toInt()
        val dp = Array(n + 1) {IntArray(minProfit + 1)}
        for (j in 0..n) { dp[j][0] = 1 }
        for (i in group.indices) {
            for (j in n downTo group[i]) {
                for (k in minProfit downTo 0) {
                    dp[j][k] = (dp[j][k] + dp[j - group[i]][Math.max(0, k - profit[i])]) % mod
                }
            }
        }
        return dp[n][minProfit]
    }
}

刷题总结

前几天介绍的题目难度较小，可能只是笔试面试题目的下限，这个题目难度较大，可能达到了笔试面试题目的上限，如果出现是压轴的题目，如果面试中能够手撕出来，基本上本轮面试的算法部分就可以通过了。