问题描述:

I am attempting to solve a problem of the following kind using dynamic programming - I can't seem to find the recurrence. The problem is as follows :

"A building is a structure formed by a pile of at least two blocks.

Your task is to find total ways, such that all blocks are utilized in making buildings.

For example, for n = 5 the answer is 2 because [5] , [2 , 3] .

For n = 6 the answer is 4 because [6] , [2 , 4] , [2 ,2 ,2] , [3 ,3]"

Can someone help me understand how to do this from a bottom up or top down manner?

This has the same idea as the partition problem. Let `f[i][j]`

detone the number of partitions of `i`

in blocks of non-decreasing size such that the last block size is `j`

. Your update rule, then, would be:

```
f[i+k][k] += f[i][j], for k>= max(2, j) // bottom-up approach
```

and the answer for the number of partitions:

```
f[n][2] + f[n][3] + ... + f[n][n]
```

Alternatively, you could use top-down approach:

```
f[i][j] += f[i-k][k] for 2 <= k <= j
```

Running this on your examples you have:

```
Initialize f[i][i] = 1, i >= 2 and the rest set to 0
f[2][2] = 1
f[3][2] = f[1][2] = 0
f[3][3] = 1
f[4][2] = f[2][2] = 1
f[4][3] = f[1][2] + f[1][3] = 0
f[4][4] = 1
f[5][2] = f[3][2] = 0
f[5][3] = f[2][2] + f[2][3] = 1
f[5][4] = f[1][2] + f[1][3] + f[1][4] = 0
f[5][5] = 1
f[6][2] = f[4][2] = 1
f[6][3] = f[3][2] + f[3][3] = 1
f[6][4] = f[2][2] + f[2][3] + f[2][4] = 1
f[6][5] = f[1][2] + f[1][3] + f[1][4] + f[1][5] = 0
f[6][6] = 1
count(5) = f[5][2] + f[5][3] + f[5][4] + f[5][5] = 2
count(6) = f[6][2] + f[6][3] + f[6][4] + f[6][5] + f[6][6] = 4
```

There's actually a really simple solution to this: the number of partitions of `n`

that contain a `1`

equals the total number of partitions of `(n - 1)`

. One way to think of it is imagining removing one `1`

from each of the partitions of `n`

that contain one; any partition of `n`

that does not contain a `1`

cannot be transformed in such a way.

So we can simply remove the first term from the classic partition recurrence, `p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) − p(k − 22) − ...`

, and derive:

```
p_without_1s(k) = p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) − p(k − 22) − ...
```

Or

```
p_without_1s(k) = p(k) - p(k - 1)
```