<p>There is a group of <code>n</code> members, and a list of various crimes they could commit. The <code>i<sup>th</sup></code> crime generates a <code>profit[i]</code> and requires <code>group[i]</code> members to participate in it. If a member participates in one crime, that member can&#39;t participate in another crime.</p>

<p>Let&#39;s call a <strong>profitable scheme</strong> any subset of these crimes that generates at least <code>minProfit</code> profit, and the total number of members participating in that subset of crimes is at most <code>n</code>.</p>

<p>Return the number of schemes that can be chosen. Since the answer may be very large, <strong>return it modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 5, minProfit = 3, group = [2,2], profit = [2,3]
<strong>Output:</strong> 2
<strong>Explanation:</strong> To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
<strong>Output:</strong> 7
<strong>Explanation:</strong> To make a profit of at least 5, the group could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>0 &lt;= minProfit &lt;= 100</code></li>
	<li><code>1 &lt;= group.length &lt;= 100</code></li>
	<li><code>1 &lt;= group[i] &lt;= 100</code></li>
	<li><code>profit.length == group.length</code></li>
	<li><code>0 &lt;= profit[i] &lt;= 100</code></li>
</ul>

// class Solution {
// public:
//     int m;
//     int dp[102][102][102];
//     int 
//     int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
//         m=profit.size();
//         memset(dp,-1,sizeof(dp));
//         return fun(0,0,0,n,minProfit,group,profit,m);

        
//     }
// };
class Solution {
public:
    const long long int MOD = (1e9) + 7;
    long long int N;
    //  t[index][profit][people]
    long long t[101][101][101];
    long long int solve(int index, int profit_, int people, int &minProfit, vector<int>& group, vector<int>& profit){
        // if no. of people increases the allowed group size then that scheme will not be taken
        if (people > N) return 0;

        //if index goes out of bound then check if profitable schemes
        if (index >= group.size()){
            if (profit_ >= minProfit){
                return t[index][profit_][people] = 1;
            }else{
                return t[index][profit_][people] = 0;
            }
        }
        // in memoization, if found then return
        if (t[index][profit_][people] != -1){
            return t[index][profit_][people];
        }
        // basic 0-1 knapsack approach of inclusion and exclusion of the certain scheme

        // if any scheme needs to be considered then !!index!! increases for sure, 
        // !!profit_!! will also increase and people will increase

        long long int will_taken = solve(index + 1, min(minProfit, profit_ + profit[index]), people + group[index], minProfit, group, profit) % MOD;

        // if any scheme needs not to be considered then !!index!! increases for sure, 
        // !!profit_!! will also remain same and people will remain same

        long long int will_not_taken = solve(index + 1, profit_, people, minProfit, group, profit) % MOD;

        return t[index][profit_][people] = (will_taken % MOD + will_not_taken % MOD) % MOD; 
    }

    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        N = n;
        memset(t, - 1, sizeof(t));
        return solve(0, 0, 0, minProfit, group, profit);
    }
};
19150