### PROBLEM LINK:

**Author:** nmalviya1929

**Editorialist:** nmalviya1929

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

DP

### PROBLEM:

Find the number of ways to divide n days into groups such that each group have at least k days.

### QUICK EXPLANATION:

Let dp[i] represent answer for i days. Then dp[n]=\sum_{i=0}^{n-k} dp[i].

### EXPLANATION:

Let dp[i] represent answer for i days.

If we’re solving for n days, in the last group we can keep days from k to n.If we select k days in last group then number of ways is dp[n-k] , if we select k+1 , then number of ways is dp[n-k-1] ans so on. Therefore dp[n]=\sum_{i=0}^{n-k} dp[i].

```
dp[0]=1;
for( i=1 to n) {
dp[i]=0;
for (j= i-k to 0) {
dp[i]+=dp[j];
dp[i]%=MOD;
}
}
```

However, time complexity for this solution is O(n^2).

We can store cumulative sum of dp to reduce the complexity.

cum[i]=\sum_{j=0}^{i} dp[j]

```
dp[0]=1;
cum[0]=1;
for (i=1 to n) {
dp[i]=0;
if(i-k is greater than equal to 0)
dp[i]+=(cum[i-k]);
dp[i]%=MOD;
}
cum[i]=(cum[i-1]+dp[i])%MOD;
}
```

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.