思路

我们可以使用动态规划来解决此问题。下面是详细的思考过程。

1. 定义状态 我们定义一个数组 $dp$，其中 $dp[i]$ 表示正整数 $i$ 有多少种不同的划分方案。我们的最终目标是求出 $dp[n]$。

2. 状态转移方程 为了计算 $dp[i]$，我们可以考虑构成整数 $i$ 的划分中，最后一个加数是什么。这个加数可以是 $1, 2, 3, \ldots, i$ 中的任意一个。

题目描述

一个正整数$n$可以表示成若干个正整数之和，形如:$n$ = $a_1$ + $a_2$ + $\cdots$ + $a_k$，其中$a_1$, $a_2$, $\ldots$, $a_k$是正整数，且不考虑加数的顺序（即顺序不同但组合相同视为同一种划分）。

这样的表示称为正整数$n$的一种划分。

现在给定一个正整数$n$，请求出 $n$ 有多少种不同的划分方案，并输出方案数。

输入

共一行，包含一个整数$n$。

输出

共一行，包含一个整数，表示总划分数量。

示例1

输入：

3

输出：

4

提示

对于$n = 3$，划分方案有：

• $3$
• $2 + 1$
• $1 + 2$
• $1 + 1 + 1$

示例2

输入：

4

输出：

8

提示

对于$n = 4$，划分方案有：

• $4$
• $3 + 1$
• $1 + 3$
• $2 + 2$
• $1 + 1 + 2$
• $2 + 1 + 1$
• $1 + 2 + 1$
• $1 + 1 + 1 + 1$