LC1621

class Solution
{
    const int mod = 1e9 + 7;
    vector<vector<array<int, 2>>> dp;
    int search(int n, int k, int end)
    {
        if (n == k)
            return end == 1;
        if (n < k)
            return dp[n][k][end] = 0;
        if (k == 0)
            return end == 0;
        if (n < 0)
            return 0;
        if (dp[n][k][end] != -1)
            return dp[n][k][end];

        int ret = 0;
        // end 1: the end is occupied
        // end 0: the end is not occupied
        switch (end) {
            case 0:
                ret = (ret + search(n - 1, k, 0)) % mod; // not take i
                ret = (ret + search(n - 1, k, 1)) % mod; // not take i
                break;
            case 1:
                ret = (ret + search(n - 1, k - 1, 0)) % mod; // take i, and make it a single group
                ret = (ret + search(n - 1, k - 1, 1)) % mod; // take i, and make it a single group
                ret = (ret + search(n - 1, k, 1)) % mod;     // take i, and make it a suffix to previous group
                break;
        }
        return dp[n][k][end] = ret;
    }

  public:
    int numberOfSets(int n, int k)
    {
        dp = vector<vector<array<int, 2>>>(n + 1, vector<array<int, 2>>(k + 1, array<int, 2>{-1, -1}));
        return (search(n - 1, k, 0) + search(n - 1, k, 1)) % mod;
    }
};