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**.

75% Solution Ratio

ShafinEarliest,

Rafiqul_IslamFastest, 0.2s

Rafiqul_IslamLightest, 262 kB

Rafiqul_IslamShortest, 772B

Toph uses cookies. By continuing you agree to our Cookie Policy.