<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 profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int m=group.size();
        vector<vector<long long>>dp(n+1,vector<long long>(minProfit+1,0));
        dp[0][0]=1;
        for(int k=0;k<m;k++){
            int a=group[k];
            int b=profit[k];
            vector<vector<long long>>v(n+1,vector<long long>(minProfit+1,0));
            v[0][0]=1;
            for(int i=1;i<=n;i++){
                for(int j=1;j<=minProfit;j++){
                    v[i][j]=dp[i][j];
                    if(i>=a){
                        int c=max(0,j-b);
                        v[i][j]+=dp[i-a][c];
                        v[i][j]%=1000000007;
                    }
                }
            }
            dp=v;
        }
        long long ans=0;
        for(int i=0;i<=n;i++){
            ans+=dp[i][minProfit];
            ans%=1000000007;
        }
        return ans;
    }*/
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
    int m = group.size();
    vector<vector<long long>> dp(n + 1, vector<long long>(minProfit + 1, 0));
    dp[0][0] = 1;

    for (int k = 0; k < m; k++) {
        int a = group[k];
        int b = profit[k];
        vector<vector<long long>> v(n + 1, vector<long long>(minProfit + 1, 0));

        // Copy current dp table to v
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= minProfit; j++) {
                v[i][j] = dp[i][j];
            }
        }

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= minProfit; j++) {
                if (i >= a) {
                    int c = max(0, j - b);
                    v[i][j] = (v[i][j] + dp[i - a][c]) % 1000000007;
                }
            }
        }

        dp = v;
    }

    long long ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = (ans + dp[i][minProfit]) % 1000000007;
    }

    return ans;
}

};
94330