盈利计划

/*
题目思路：
1. 使用动态规划来解决问题。
2. 定义一个三维数组 dp，dp[i][j][k] 表示前 i 个工作中，使用 j 个员工，获得至少 k 利润的方案数。
3. 初始化 dp[0][0][0] = 1，表示不使用任何员工且没有利润的情况。
4. 遍历每个工作，并更新 dp 数组。
5. 对每个工作，考虑两种情况：不选该工作和选该工作。
6. 最后统计 dp 数组中利润至少为 minProfit 的方案总数。
*/

import java.util.stream.IntStream;

public class ProfitableSchemesStream {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int MOD = 1000000007;
        int length = group.length;
        int[][][] dp = new int[length + 1][n + 1][minProfit + 1];
        dp[0][0][0] = 1;

        for (int i = 1; i <= length; i++) {
            int members = group[i - 1];
            int earn = profit[i - 1];
            IntStream.rangeClosed(0, n).forEach(j -> IntStream.rangeClosed(0, minProfit).forEach(k -> {
                dp[i][j][k] = dp[i - 1][j][k];
                if (j >= members) {
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - members][Math.max(0, k - earn)]) % MOD;
                }
            }));
        }

        return IntStream.rangeClosed(0, n).map(j -> dp[length][j][minProfit]).reduce(0, (a, b) -> (a + b) % MOD);
    }
}