Counting Integer Partitions

This problem asks you to determine the number of distinct partitions of a positive integer n. A partition of n represents a way of writing n as a sum of positive integers, where the order of the summands is not important.

For example, the partitions of 4 are:
$$4,\;3+1,\;2+2,\;2+1+1,\;1+1+1+1$$ which gives a total of 5 partitions.

Your task is to implement a function that computes the number of partitions for a given positive integer n.

Note: The underlying idea is based on dynamic programming. In the algorithm, we use a two-dimensional table to represent subproblems. The recurrence relation is defined as follows:

$$dp[i][j]=\begin{cases}dp[i-1][j]+dp[i][j-i] & \text{if } i\le j,\\ dp[i-1][j] & \text{if } i>j.\end{cases}$$

inputFormat

Input consists of a single integer n read from standard input.

Constraints: 1 ≤ n ≤ 100 (you may assume that n is a small positive integer).

outputFormat

The output is a single integer, representing the number of distinct partitions of n, printed to standard output.

## sample

4

5

</p>