1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
#include <vector>

const int M = 1'000'000'007;

class Solution {
public:
    int profitableSchemes(int n, int minProfit, std::vector<int>& group, std::vector<int>& profit) {
        int m = group.size();
        std::vector<std::vector<int>> dp(n + 1, std::vector<int>(minProfit + 1));
        
        dp[0][0] = 1;
        for (int s = 0; s < m; ++s) {
            for (int i = n; i >= group[s]; --i) {
                for (int j = minProfit; j >= 0; --j) {
                    dp[i][j] = (dp[i][j] + dp[i - group[s]][std::max(0, j - profit[s])]) % M;
                }
            }
        }
        
        long long sum = 0;
        for (int i = 0; i <= n; ++i) {
            sum += dp[i].back();
        }
        
        return sum % M;
    }
};