DP问题——整数划分

原题链接：

900. 整数划分 - AcWing题库https://www.acwing.com/problem/content/description/902/

#include#includeusing namespace std;const int N = 1010;int dp[N][N];//最大方案数int n;int mod = 1e9 + 7;int main() {cin >> n;for (int i = 0; i <= n; i++) {dp[i][0] = 1;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {for (int k = 0; k*i <= j; k++) {dp[i][j] = (dp[i - 1][j - k * i]+dp[i][j]) % mod;}}}cout << dp[n][n] << endl;return 0;}