【题目来源】
AcWing：900. 整数划分 - AcWing题库
【题目描述】
一个正整数 \(n\) 可以表示成若干个正整数之和，形如：\(n=n_1+n_2+...+n_k\)，其中 \(n_1\ge n_2\ge ...\ge n_k,k\ge 1\)。
我们将这样的一种表示称为正整数 \(n\) 的一种划分。
现在给定一个正整数 \(n\)，请你求出 \(n\) 共有多少种不同的划分方法。
【输入】
共一行，包含一个整数 \(n\)。
【输出】
共一行，包含一个整数，表示总划分数量。
由于答案可能很大，输出结果请对 \(10^9+7\) 取模。
【输入样例】
5
【输出样例】
7
【解题思路】
【算法标签】
《AcWing 900 整数划分》 #动态规划# #计数类DP#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N=1010, MOD=1e9+7; //数据最大1000
int n, f[N][N]; //f[i][j] 从1-i个数中选数和正好是j的选法集合
int main()
{cin >> n;for (int i=0; i<=n; i++)f[i][0] = 1; //边界，前i个数和是0，一个都不选for (int i=1; i<=n; i++) //前n个物品（数）for (int j=0; j<=n; j++) { //体积和等于j（前i数之和为j）f[i][j] = f[i-1][j]; //数i不选if (j>=i) { //数i：不选+可以选f[i][j] = (f[i-1][j] + f[i][j-i]) % MOD;}}cout << f[n][n] << endl; return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N=1010, MOD=1e9+7; //数据最大1000
int n, f[N]; //f[j] 从1-i个数中选数和正好是j的选法集合
int main()
{cin >> n;f[0] = 1; //边界for (int i=1; i<=n; i++) //前n个物品（数）for (int j=0; j<=n; j++) { //体积和等于j（前i数之和为j）f[j] = f[j]; //数i不选if (j>=i) { //数i：不选+可以选f[j] = (f[j] + f[j-i]) % MOD;}}cout << f[n] << endl; return 0;
}
【运行结果】
5
7