Leetcode 879. profit plan

LeetCode 879. Profit plan

Multidimensional 01 knapsack problem

const int N = 110, MOD = 1e9 + 7;
class Solution {
    
public:
    int f[N][N][N] = {
    0};// Before presentation i A job , The number of people does not exceed j, Profit does not exceed k Number of alternatives 
    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 A job , Profit is 0 It's a legal plan .

        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];
    }
};

Space optimization

const int N = 110, MOD = 1e9 + 7;
class Solution {
    
public:
    int f[N][N] = {
    0};// Before presentation i A job , The number of people does not exceed j, Profit does not exceed k Number of alternatives 
    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];
    }
};