879. 盈利计划 难

879. 盈利计划

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。

输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
总的来说，有两种计划。

//三维dp ，时空lmn
func profitableSchemes(n, minProfit int, group, profit []int) (sum int) {
    const mod int = 1e9 + 7
    ng := len(group)
    dp := make([][][]int, ng+1)
    for i := range dp {
        dp[i] = make([][]int, n+1)
        for j := range dp[i] {
            dp[i][j] = make([]int, minProfit+1)
        }
    }
    dp[0][0][0] = 1
    for i, members := range group {
        earn := profit[i]
        for j := 0; j <= n; j++ {
            for k := 0; k <= minProfit; k++ {
                if j < members {
                    dp[i+1][j][k] = dp[i][j][k]
                } else {
                    dp[i+1][j][k] = (dp[i][j][k] + dp[i][j-members][max(0, k-earn)]) % mod
                }
            }
        }
    }
    for _, d := range dp[ng] {
        sum = (sum + d[minProfit]) % mod
    }
    return
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

//二维dp
func profitableSchemes(n, minProfit int, group, profit []int) (sum int) {
    const mod int = 1e9 + 7
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, minProfit+1)
        dp[i][0] = 1
    }
    for i, members := range group {
        earn := profit[i]
        for j := n; j >= members; j-- {
            for k := minProfit; k >= 0; k-- {
                dp[j][k] = (dp[j][k] + dp[j-members][max(0, k-earn)]) % mod
            }
        }
    }
    return dp[n][minProfit]
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}