LeetCode 879. 盈利计划

LeetCode 879. 盈利计划

多维01背包问题

const int N = 110, MOD = 1e9 + 7;
class Solution {
    
public:
    int f[N][N][N] = {
    0};//表示前i个工作，人数不超过j，利润不超过k的方案数
    int profitableSchemes(int m, int minProfit, vector<int>& g, vector<int>& p) {
    
        int n = g.size();
        for(int i = 0; i <= m; i ++) f[0][i][0] = 1; //0个工作，利润为0是一个合法方案。

        for(int i = 1; i <= n; i ++)
            for(int j = 0; j <= m; j ++)
                for(int k = 0; k <= minProfit; k ++)
                {
    
                    f[i][j][k] = f[i - 1][j][k];
                    if(j >= g[i - 1])
                        f[i][j][k] =(0LL + f[i][j][k] +  f[i - 1][j - g[i - 1]][max(0, k - p[i - 1])]) % MOD;
                }
        return f[n][m][minProfit];
    }
};

空间优化

const int N = 110, MOD = 1e9 + 7;
class Solution {
    
public:
    int f[N][N] = {
    0};//表示前i个工作，人数不超过j，利润不超过k的方案数
    int profitableSchemes(int m, int minProfit, vector<int>& g, vector<int>& p) {
    
        int n = g.size();
        for(int i = 0; i <= m; i ++) f[i][0] = 1;

        for(int i = 1; i <= n; i ++)
            for(int j = m; j >= 0; j --)
                for(int k = minProfit; k >= 0; k --)
                {
    
                    if(j >= g[i - 1])
                        f[j][k] =(0LL + f[j][k] +  f[j - g[i - 1]][max(0, k - p[i - 1])]) % MOD;
                }
        return f[m][minProfit];
    }
};