一个正整数 𝑛 可以表示成若干个正整数之和，形如：𝑛=𝑛1+𝑛2+…+𝑛𝑘，其中 𝑛1≥𝑛2≥…≥𝑛𝑘,𝑘≥1。

我们将这样的一种表示称为正整数 𝑛 的一种划分。

现在给定一个正整数 𝑛，请你求出 𝑛 共有多少种不同的划分方法。

输入格式

共一行，包含一个整数 𝑛。

输出格式

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

由于答案可能很大，输出结果请对 +7 取模。

数据范围

1≤𝑛≤1000

输入样例:

5

输出样例：

7

 代码：

1. 二维数组做法（完全背包）

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];int CountDP(){for(int i = 0;i <= n;i ++){f[i][0] = 1;}for(int i = 1;i <= n;i ++){for(int j = 1;j <= n;j ++){if(j >= i){f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;}else{f[i][j] = f[i - 1][j];}}}return f[n][n];
}int main(){cin>>n;int res = CountDP();cout<<res<<endl;return 0;
}

2. 一维数组做法（完全背包）

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 1010, mod = 1e9 + 7;
int n;
int f[N];int CountDP(){for(int i = 0;i <= n;i ++){f[0] = 1;}for(int i = 1;i <= n;i ++){for(int j = 1;j <= n;j ++){if(j >= i){f[j] = (f[j] + f[j - i]) % mod;}else{f[j] = f[j];}}}return f[n];
}

3. 优化做法（以最小值1为界划分）

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];int CountDP(){f[0][0] = 1;for(int i = 1;i <= n;i ++){for(int j = 1;j <= i;j ++){f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;}}int res = 0;for(int i = 1;i <= n;i ++){res = (res + f[n][i]) % mod;}return res;
}int main(){cin>>n;int res = CountDP();cout<<res<<endl;return 0;
}