So, the problem becomes, You are given an array of size N, you have to divide the array at most k groups in a consecutive manner.
The k can't be that large. k will be minimum of N and k.
We can approach the problem in dynamic programming. where
dp[g][i] means how many ways we can end the gth group in ith position.
To calculate dp[g][i], one approach is iterate through all the position where the gth group can be started. such that, if gth group can be started at position j then dp[g][i] += dp[g-1][j - 1] for every j. But iterating through j is not possible due to time complexity. So, we can do the cumulative sum approach, then we can get the sum for dp[g-1][j - 1] for every jth position gth group can be started.
Then the result is the summation of dp[g][n] where g = 1 to k;
There is a problem, we cant store all the value of dp[g][i] due to memory complexity. Think we don't need all the values. for calculating any dp[g][i], we need only the previous row which is using group g - 1. So here, we can use row swap every iteration of g.
