Counting Block Combinations II

NOTE: This is a more difficult version of Problem 114.
A row measuring $n$ units in length has red blocks with a minimum length of $m$ units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square.
Let the fill-count function, $F(m, n)$, represent the number of ways that a row can be filled.
For example, $F(3, 29) = 673135$ and $F(3, 30) = 1089155$.
That is, for $m = 3$, it can be seen that $n = 30$ is the smallest value for which the fill-count function first exceeds one million.
In the same way, for $m = 10$, it can be verified that $F(10, 56) = 880711$ and $F(10, 57) = 1148904$, so $n = 57$ is the least value for which the fill-count function first exceeds one million.
For $m = 50$, find the least value of $n$ for which the fill-count function first exceeds one million.

This problem can be solved using dynamic programming.

Let f[i] = the number of ways to fill a row of length i.

Define that a row of zero length can be filled in 1 way (no blocks).

f[i] = f[i-1] + f[i-m-1] + f[i-m-1 – 1] + f[i-m-1 – 2] + … + f[0] for i >= m
f[i] = f[i-1] for i < m In English, the interpretation is as follows: To fill a row of length n, one can either not place a block at the end, leaving a length of n-1 to be filled, which can be done in f[n-1] ways, or one can place a block of length m followed by a black square, leaving a length of n-m-m to be filled, which can be done in f[n-m-1] ways, or one can place a block of length m+1 followed by a black square, leaving a length of n-m-1 - 1 to be filled, which can be done in f[n-m-1 - 1] ways...and so on. Thus f[n] equals sum of all these possibilities. In our case, m = 50. We can use this formula to recursively compute f[n] for increasing values of n until the first value of n for which f[n] exceeds one million. This will give us the smallest value of n for which F(50, n) exceeds one million. Please note that in the above discussion and formula, F(m, n) is equivalent to f[n] in our DP solution. So, we need to solve this equation using dynamic programming and find the least value of 'n' where f[n] will exceed one million.

More Answers: