Count the possible plans for nurses I am new to Algorithms and Competitive Coding. I read an exercise paper given by my teacher as below:

The director of a hospital want to schedule a working plan for a nurse
in a given period of N consecutive days 1,..., N. Due to the policy of
the hospital, each nurse cannot work all the days 1,..., N. Instead,
there must be days off in which the nurse need to take a rest. A
working plan is a sequence of disjoint working periods. A working
period of a nurse is defined to be a sequence of consecutive days on
which the nurse must work and the length of the working period is the
number of consecutive days of that working period. The hospital
imposes two constraints:
Each nurse can take a rest only one day between two consecutive
working periods. it means that if the nurse takes a rest today, then
she has to work tomorrow (1)
The length of each working period must be greater or equal to K1 and
less than or equal to K2 (2)
The director of the hospital want to know how many possible working
plans satisfying above constraint?
input
6 2 3
output
4

I have thought a lot and just give an initial idea: I will use an 1-D array to represent a schedule from day 1 to day N. for each day (ith day), I have two choices: the nurse will work this day or the nurse will not work on this day.
If the nurse does not work on the ith day, the ways for this case is the total ways of the ith-2 day. (Because she must have a day off on the previous day.
Else, the ways for this case will be the sum of total ways of the ith-j day, with j in [K1, K2].
However, I do not know why I am wrong and which way will be the correct answer. I really need your help to derive an appropriate algorithm
You can solve this problem with dynamic programming. Your states are
dp[day_number][worked_sofar]. here is a recursive implementation:
#include&lt;bits/stdc++.h&gt;

using namespace std;

vector&lt;vector&lt;int&gt; &gt; dp;
int n, k1, k2;
int solve(int day, int sofar){
    if(day &gt; n || sofar &gt; k2)return 1;
    if(dp[day][sofar] != -1)return dp[day][sofar];
    int ans = solve(day + 1, sofar + 1);
    if(sofar &gt;= k1)ans += solve(day + 1, 0);
    return dp[day][sofar] = ans;
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin &gt;&gt; n &gt;&gt; k1 &gt;&gt; k2;
    dp.assign(n + 1, vector&lt;int&gt;(k2 + 1, -1));
    cout&lt;&lt;solve(1, 0);
    return 0;
}

```