# A Knapsack problem

This is a biweekly contest problem from leetcode. We can solve it by using the idea from the knapsack problem.

In the knapsack problem, we can either take or not take.
For this one, we have 3 actions:
1a) Take the current interval and combine with the previous one
1b) Take the current interval and not combine with the previous one
2. Not take the current interval.

`long long dp;const int mod = 1e9+7;class Solution {public:    int numberOfSets(int n, int k) {        memset(dp, 0, sizeof(dp));        //in i,j, k. For the k: 0 means not take, 1 means take        dp = 1;        for (int i = 1; i < n;++i) {            for (int j = 0; j <= k; ++j) {                // take this block to combine with previous                dp[i][j] += dp[i-1][j];                // take this block as a separate one                if(j>0)dp[i][j] += dp[i-1][j-1];                if(j>0)dp[i][j] += dp[i-1][j-1];                // not take this block                dp[i][j] += dp[i-1][j];                dp[i][j] += dp[i-1][j];                if (dp[i][j]>=mod)dp[i][j]%=mod;                if (dp[i][j]>=mod)dp[i][j]%=mod;            }        }        long long ret = dp[n-1][k] +  dp[n-1][k];        if (ret >= mod) ret %= mod;        return ret;         }};`

Hope it helps.

--

--