Count Staircases Built from n Blocks with Strictly Increasing Step Heights

You have `n` identical unit blocks. A staircase is a row of one or more steps, each step a column of blocks, where every step has a positive height and each step is strictly taller than the step before it. Count how many different staircases use all `n` blocks exactly. A staircase made of a single step of height `n` also counts. ### Function Signature ```python def count_staircases(n: int) -> int: ``` ### Rules - A staircase is described by its step heights from left to right, `h1 < h2 < ... < hk`, with `k >= 1`, every `hi >= 1`, and `h1 + h2 + ... + hk == n`. - Two staircases are different when their lists of heights differ. Because the heights must strictly increase, the order of the steps is fixed, so a staircase is the same thing as a set of distinct positive integers that sum to `n`. - The single step `[n]` counts as one staircase. - Return the number of different staircases. ### Constraints - `1 <= n <= 500` - The answer exceeds `2^31 - 1` for the larger values of `n` in this range, so use a 64-bit or arbitrary-precision integer. For every `n` in the range, the answer is below `2^53`. ### Examples **Example 1** ```text Input: n = 1 Output: 1 ``` The only staircase is a single step of height 1. **Example 2** ```text Input: n = 6 Output: 4 ``` The staircases are `[6]`, `[1, 5]`, `[2, 4]` and `[1, 2, 3]`. `[3, 3]` is not allowed because the heights must strictly increase. **Example 3** ```text Input: n = 10 Output: 10 ``` The staircases are `[10]`, `[1, 9]`, `[2, 8]`, `[3, 7]`, `[4, 6]`, `[1, 2, 7]`, `[1, 3, 6]`, `[1, 4, 5]`, `[2, 3, 5]` and `[1, 2, 3, 4]`.