题目：整数拆分

题目描述

给定一个正整数 $n$，将其拆分成至少两个正整数的和，计算所有不同拆分方案的数量。不同的拆分方案指拆分出的正整数序列不同。例如，当 $n = 4$ 时，有以下拆分方案：$(1 + 1 + 1 + 1)$、$(1 + 1 + 2)$、$(1 + 3)$、$(2 + 2)$，拆分方案数量为 $4$。

请使用递归的方法编写一个程序，计算并输出正整数 $n$ 的拆分方案数量。

输入格式

一个正整数 $n$（$2\leq n\leq 20$）。

输出格式

一个整数，表示正整数 $n$ 的拆分方案数量。

示例

• 输入：

4

• 输出：

4

提示

可以定义一个递归函数来解决该问题。递归的关键在于问题的分解。对于将 $n$ 进行拆分，可考虑以某个数 $i$ 作为拆分的一部分，然后对剩余的 $n - i$ 继续进行拆分。为避免重复计算，在递归过程中要保证拆分出的数呈递增顺序。即拆分 $n$ 时从某个数 $i$ 开始，后续对 $n - i$ 拆分时选取的数要大于等于 $i$，以此确保每种拆分方案仅被计算一次。