LeetCode 879. 盈利计划

Categories:

题目描述
思路分析
1. 解法一：二维 DP（推荐）
相似题目

题目描述

✅ 879. 盈利计划

思路分析

解法一：二维 DP（推荐）

核心思路：

dp[p][j] 表示使用 j 人达到利润 p（利润封顶为 minProfit）的方案数。

对每个任务逆序更新人数维度，利润维度做封顶转移。

最终答案为 sum(dp[minProfit][j])。

复杂度分析：

时间复杂度：O(m _ n _ P)，其中 m 表示任务数，n 为人数上限，P 为 minProfit。

空间复杂度：O(n * P)。

class Solution {
    private static final int MOD = 1_000_000_007;

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int[][] dp = new int[minProfit + 1][n + 1];
        dp[0][0] = 1;

        for (int i = 0; i < group.length; i++) {
            int g = group[i];
            int p = profit[i];
            for (int j = n; j >= g; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    int nk = Math.min(minProfit, k + p);
                    dp[nk][j] = (dp[nk][j] + dp[k][j - g]) % MOD;
                }
            }
        }

        int ans = 0;
        for (int j = 0; j <= n; j++) {
            ans = (ans + dp[minProfit][j]) % MOD;
        }
        return ans;
    }
}

func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
	const mod = 1_000_000_007
	dp := make([][]int, minProfit+1)
	for i := 0; i <= minProfit; i++ {
		dp[i] = make([]int, n+1)
	}
	dp[0][0] = 1

	for i := 0; i < len(group); i++ {
		g := group[i]
		p := profit[i]
		for j := n; j >= g; j-- {
			for k := minProfit; k >= 0; k-- {
				nk := k + p
				if nk > minProfit {
					nk = minProfit
				}
				dp[nk][j] = (dp[nk][j] + dp[k][j-g]) % mod
			}
		}
	}

	ans := 0
	for j := 0; j <= n; j++ {
		ans = (ans + dp[minProfit][j]) % mod
	}
	return ans
}

相似题目

题目	难度	考察点
494. 目标和	中等	DP
416. 分割等和子集	中等	背包 DP
518. 零钱兑换 II	中等	背包 DP
322. 零钱兑换	中等	背包 DP
1049. 最后一块石头的重量 II	中等	背包 DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/77065409