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[1001][1001][2];
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[0][0][0] = 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][1] += dp[i-1][j][1];
// take this block as a separate one
if(j>0)dp[i][j][1] += dp[i-1][j-1][1];
if(j>0)dp[i][j][1] += dp[i-1][j-1][0];
// not take this block
dp[i][j][0] += dp[i-1][j][0];
dp[i][j][0] += dp[i-1][j][1];
if (dp[i][j][0]>=mod)dp[i][j][0]%=mod;
if (dp[i][j][1]>=mod)dp[i][j][1]%=mod;
}
}
long long ret = dp[n-1][k][0] + dp[n-1][k][1];
if (ret >= mod) ret %= mod;
return ret;
}
};

Hope it helps.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi