A Knapsack problem

1621. Number of Sets of K Non-Overlapping Line Segments

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.