leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0879.cpp (659B)


      1 class Solution {
      2   public:
      3     int profitableSchemes(int n, int minProfit, const vector<int> &group, const vector<int> &profit) {
      4         int dp[101][101] = {{1}};
      5         int res = 0, mod = 1e9 + 7;
      6         for (int k = 0; k < group.size(); k++) {
      7             int g = group[k], p = profit[k];
      8             for (int i = minProfit; i >= 0; i--) {
      9                 for (int j = n - g; j >= 0; j--) {
     10                     int &cache = dp[min(i + p, minProfit)][j + g];
     11                     cache = (cache + dp[i][j]) % mod;
     12                 }
     13             }
     14         }
     15         for (int x : dp[minProfit])
     16             res = (res + x) % mod;
     17         return res;
     18     }
     19 };