您现在的位置是：首页 >技术教程 >leetcode 879. Profitable Schemes（有利润的计划）网站首页技术教程

有几个工程，每个工程需要group[ i ]个人去做，做完了可以得到profit[ i ]的利润。
现有2个限制条件：
人数上限是n, 且参加了一个工程的人不能再参加其他工程。
利润下限minProfit, 至少要获得minProfit的利润。
问有多少种工程的选法，可以满足在<=n个人时，能达到>=minProfit的利润。

思路：

1.三维DP

整体有点复杂，从简单的例子入手，
拿Example1来说，
dp[i][j][k] 代表前 i个工程，选 j 个人参加， 最小利润是 k
这里i从1开始，所以i>=1 && i <= group.length, 0 <= j <= n, 0 <= k <= minProfit（k越小，可选的工程越多）

如果只是一个限制条件，那么二维DP，现在有2个限制条件，先看三维DP，后面再简化到二维。

初始条件，0个工程，0个人，最小利润是0，这种情况有一种scheme, 就是什么都不干（不干也是一种方法）。
所以 dp[0][0][0] = 1.

i= 1, j = 0, k = 0, 即1个工程，限制人数不能超过0个人，下限利润为0，
人数限制在0个，谁都不能干，所以干不了，可选的方法数和dp[0][0][0]一样。
dp[1][0][0] = dp[0][0][0] = 1
不管再来几个工程，也还是干不了，dp[i][0][k] = dp[i-1][0][0]
如果还是0个人，把利润k 抬高，直到minProfit, 都干不了，还保持在dp[0][0][0]
即 dp[i][0][k] = dp[i-1][0][0]

所以只要group[i]的人数 > j (超过人数限制），这个工程就干不了，只能选择不干，状态保持在上一个工程
dp[i][j][k] = dp[i-1][j][k]

上面j =0, 1都是这个情况，
现在把人数上限增加到2, 即 j = 2，
第1个工程，需要人数group[i-1], 能赚到profit[i-1], (ℹ是第几个工程，从1开始）
现在group[0] = 2 <= j， 能干，
利润下限为k ,
如果接了这个工程后利润下限为k, 那么到上一工程为止利润下限为max(0, k - profit[i-1])
接了该工程后人数上限为 j, 那么在接这个工程前人数上限为j - group[i-1],
所以如果接这个工程，上一状态就应该是dp [ i-1 ] [ j-groups[i-1] ] [ max(0, k - profit[i-1]) ]

当然也可以选择不干这个工程，那么就是两种情况，干与不干。

所以在 group[i-1] < j时（人数没超过上限）
dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-groups[i-1]][max(0, k - profit[i-1])] (可干可不干两种情况）

最后的结果是当最后一个工程为止，选 0 ~ n 个人参与时，下限利润为minProfit的schme之和。
也就是对 j = 0~n的情况求和，dp [ group.length ] [ j ] [ minProfit ]

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length;
        int[][][] dp = new int[len+1][n+1][minProfit+1];
        dp[0][0][0] = 1;
        int sum = 0;
        int mod = (int)1e9+7;
        //dp[i][j][k]:j个worker被选到前i个crime中，下限profir是k
        //最后需要的结果：sum_{j}(dp[len][j][minProfit]),也就是说可以选1～n个人来做,
        //前len个crime,下限profit是minProfit

        for(int i = 1; i <= len; i++) { //前n个crime  
            int members = group[i-1];
            int money = profit[i-1];          
            for(int j = 0; j <= n; j++) {  //选j个人参与     
                for(int k = 0; k <= minProfit; k++) {
                    if(members > j)//group[j]的人不能干第i个crime(超过人数了),方式不会增多
                        dp[i][j][k] = dp[i-1][j][k] % mod;
                    //group[i]的人要干第i个crime,那么其他的j-group[i]的人就干前i-1个crime
                    else   //group[i]能干第i个crime,在原有方式数的基础上增加新的ways,该crime可参与可不参与
                        dp[i][j][k] = (dp[i-1][j][k] + dp[i-1][j-members][Math.max(0, k-money)])%mod;
                }
            }
        }

        //挑选1~n个人来做前len个crime,下限是minProfit
        for(int i = 0; i <= n; i++)
            sum = (sum + dp[len][i][minProfit]) % mod;
        return sum;
    }

2.二维DP

前面三维DP中可以看到dp[i] [… ] [… ] 只与dp[i-1] […] […]有关
所以考虑去掉 i 这一维，直接在二维dp上更新，

可以看到在group [ i ] > j 时 dp [ i ] […] […]是维持在dp[i-1] […] […]不变的，
所以这种情况下不需要更新二维DP，只需考虑 group [ i ] <= j 的情况，
因此限制 j 在 group[i] ~ n 范围。

需要注意的是这种情况下， j, k 必须是降序递减。
具体原因写在注释里面。

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length;
        int[][] dp = new int[n+1][minProfit+1];
        dp[0][0] = 1;
        int sum = 0;
        int mod = (int)1e9+7;
        //dp[i][j][k]:j个worker被选到前i个crime中，下限profit是k
        //最后需要的结果：sum_{j}(dp[len][j][minProfit]),也就是说可以选1～n个人来做,
        //前len个crime,下限profit是minProfit

        for(int i = 1; i <= len; i++) { //前n个crime  
            int members = group[i-1];
            int money = profit[i-1];          
            for(int j = n; j >= members; j--) {  //选j个人参与     
                for(int k = minProfit; k >= 0; k--) {
                    //j < members时: 维持在dp[i-1]这个维度的值，不需要更新
                    
                    //现在只考虑j>=members的情况:
                    //如果想去掉i维度，原则是一旦dp[j][k]被更新，后面不能再用第二次，
                    //因为用第二次相当于dp[i-1][j][k]已经变了，不是原来的值了

                    //如果j,k是从小到大递增，那么一旦dp[j][k]被更新（相当于dp[i-1][j][k]被更新了）
                    //而后面j增大，j-members还有可能得到原来更新过的较小的j，会影响结果
                    //而j,k从大到小，先更新的是较大的j,k处，一旦更新一次，后面不会再用到
                    //因为j-members,k-money只会更小，不会得到原来较大的值
                    //dp[i][j][k] = (dp[i-1][j][k] + dp[i-1][j-members][Math.max(0, k-money)])%mod;
                    dp[j][k] = (dp[j][k] + dp[j-members][Math.max(0, k-money)]) % mod;
                }
            }
        }

        //挑选1~n个人来做前len个crime,下限是minProfit
        for(int i = 0; i <= n; i++)
            sum = (sum + dp[i][minProfit]) % mod;
        return sum;
    }