ACM，OI等比赛，整数划分为常见的入门题，许久没打比赛，最近做笔试题突然碰到，磕磕绊绊了很久才搞清楚，现在做个笔记。
-------------------------------------------------------------------------------------
题目可见hduoj1028 , 简单的讲：
数字N，整数划分的组合数为多少。整数划分表示正整数的和集为N，比如N=4时：
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
有这5中情况，所以N=4的整数划分的组合数为5。
-------------------------------------------------------------------------------------
解题，开始DP，先对DP进行状态的设计：
思考的第一步： 考虑到是组合，不能出现重复的情况，比如4=3+1与4=1+3是一种，所以采用“划分数中的最大值”来限定重复状态。
思考的第二步：状态设计：dp[n][n]表示“和为n、最大划分数为m”时，组合的数量。
思考的第三步：状态转移：由划分数中是否包含m分为两种状态，当前组合数等于这两种状态下的组合数之和。
递归比较方便，先放记忆化递归的代码：
#include<iostream> using namespace std; const int MAXN = 128; int dp[MAXN][MAXN] = {0}; int DP(int n, int m) { // 不合法情况 if (n <= 0 || m <= 0) return 0; // 记忆化 if (dp[n][m] > 0) return dp[n][m]; // 1. n=1只有一种{1}; // 2. m=1只有一种{1,1,1,,,,,,} if (n == 1 || m == 1) return dp[n][m] = 1; // 1. 包含m只有一种{m} // 2. 不包含m, dp[n][m-1] // n==m,这两种情况为所有情况 if (n == m) return dp[n][m] = 1 + DP(n, m - 1); // m最大也只能是n if (n < m) return dp[n][m] = DP(n, n); // 1. 包含m, 将最后一个数定为m, dp[n-m][m] // 2. 不包含m, 最大的数为m-1, do[n][m-1] // n>m,这两种情况为所有情况 if (n > m) return dp[n][m] = DP(n - m, m) + DP(n, m - 1); // 不合法情况 return dp[n][m] = 0; } int main() { int n; while (cin >> n) { cout << DP(n, n) << endl; } return 0; }
DP递推版
#include<iostream> using namespace std; const int MAXN = 128; int dp[MAXN][MAXN] = { 0 }; void init(int maxn) { for (int n = 1; n <= maxn; n++) { for (int m = 1; m <= maxn; m++) { // n=1时，无论m等于多少，都只有一种{1}的划分，dp[1][m] = 1 // m = 1时，无论n等于多少，都只有一种{ 1,1,1,,,,,, }的划分，dp[n][1] = 1 if (n == 1 || m == 1) dp[n][m] = 1; // n==m时，分两种情况，dp[n][m] = 1 + dp[n][m-1]： // 1. 划分数中包含m时，只有一种{ m } // 2. 划分数中不包含m时，那最大值只能是m - 1，为dp[n][m - 1] else if (n == m) dp[n][m] = 1 + dp[n][m-1]; // n>m时，m最大也只能取n，dp[n][m] = dp[n][n] else if (n < m) dp[n][m] = dp[n][n]; // n<m时，分两种情况，dp[n][m] = dp[n-m][m] + dp[n][m-1]: // 1. 划分数中包含m时，最后一个划分数必须为m（前面也可以有m）sum{........m}=n，dp[n-m][m] // 2. 划分数中不包含m时，那最大划分数只能是m-1，dp[n][m-1] else if (n > m) dp[n][m] = dp[n - m][m] + dp[n][m - 1]; } } } int main() { init(120); int n; while (cin >> n) { cout << dp[n][n] << endl; } return 0; }
-------------------------------------------------------------------------------------
现在考虑一些更加复杂的情况
-------------------------------------------------------------------------------------
原文：https://www.cnblogs.com/taoshiqian/p/11519113.html