![](/static/253f0d9/assets/icons/icon-96x96.png)
![](https://programming.dev/pictrs/image/9fcac0c0-32b5-40c9-bb7c-53bc37d32884.png)
T counts the number of ways to place the blocks with lengths specified in b in the remaining a.size - ai slots. If there are no more slots left, there are two cases: Either there are also no more blocks left, then everything is fine, and the current situation is 1 way to place the blocks in the slots. Otherwise, there are still blocks left, and no more space to place them in. This means the current sitution is incorrect, so we contribute 0 ways to place the blocks. This is what the if bi >= b.size then 1L else 0L
does.
The start at size + 1
is necessary, as we need to compute every table entry before it may get looked up. When placing the last block, we may check the entry (ai + b(bi) + 1, bi + 1)
, where ai + b(bi)
may already equal a.size
(in the case where the block ends exactly at the end of a
). The + 1
in the entry is necessary, as we need to skip a slot after every block: If we looked at (ai + b(bi), bi + 1)
, we could start at a.size
, but then, for e.g. b = [2, 3]
, we would consider ...#####.
a valid placement.
Let me know if there are still things unclear :)
If you make the recurrent case a little more complicated, you can sidestep the weird base cases, but I like reducing the endpoints down to things like this that are easily implementable, even if they sound a little weird at first.