思路
我们可以使用动态规划来解决此问题。下面是详细的思考过程。
-
定义状态
我们定义一个数组 dp，其中 dp[i] 表示正整数 i 有多少种不同的划分方案。我们的最终目标是求出 dp[n]。
-
状态转移方程
为了计算 dp[i]，我们可以考虑构成整数 i 的划分中，最后一个加数是什么。这个加数可以是 1,2,3,…,i 中的任意一个。
P3637.整数划分(无序版本)
题目描述
一个正整数n可以表示成若干个正整数之和，形如:n = a1 + a2 + ⋯ + ak，其中a1, a2, …, ak是正整数，且不考虑加数的顺序（即顺序不同但组合相同视为同一种划分）。
这样的表示称为正整数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
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
