Description

Submission

class Solution {
    const int M = 1e9+7;
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        vector<vector<int>> dp(n+1, vector<int>(minProfit+1, 0));
        dp[0][0] = 1;

        for(int k = 0; k < group.size(); ++k) {
            int x = group[k];
            int y = profit[k];
            
            auto tmp = dp;

            for(int i = 0; i <= n; ++i) {
                for(int j = 0; j <= minProfit; ++j) {
                    if(i + x <= n) {
                        int p = min(j + y, minProfit);
                        dp[i+x][p] += tmp[i][j];
                        dp[i+x][p] %= M;
                    }
                }
            }
        }

        int ret = 0;
        for(int i = 0; i <= n; ++i) {
            ret += dp[i][minProfit];
            ret %= M;
        }

        return ret;
    }
};
// dp[n_person][profit]: number of ways to get profit with n_person.