题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1028
题目大意：
整数拆分，给一个整数n,求它有多少种拆分方法。
题目思路：
做法一：
d[i][j]表示把整数 i 拆成最多 j 个数字所具有的方法数。那么
if (i >ｊ) d[i][j] = d[i-j][j] + d[i][j-1]; 意思就是如果i>j，那么有两种方式：一种是先把i里面分理处j个1，然后再把i-j拆成最多i-j个数字；另一种是把i拆分成最多j-1个数字。
if (i < j) d[i][j] = d[i][i]; 意思就是如果i<j，那么这种情况和把数字i最多拆成i个数字的是一样的。
if (i == j) d[i][j] = d[i][j-1] + 1; 意思就是如果i==j，那么可以把数字i拆分成j-1个数字，也可以把数字i拆分成i个1（这个就是那个1的意义）
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 #define LL long long 7 int d[140][140], n; 8 void init() { 9 while (~scanf("%d", &n)) { 10 int i, j; memset(d, 0, sizeof(d)); 11 for (i = 0; i <= n; ++i) d[i][1] = d[1][i] = 1; 12 for (i = 2; i <= n; ++i) { 13 for (j = 1; j <= n; ++j) { 14 if (i > j) d[i][j] = d[i-j][j] + d[i][j-1]; 15 else if (i == j) d[i][j] = 1 + d[i][j-1]; 16 else d[i][j] = d[i][i]; 17 } 18 } 19 cout << d[n][n] << endl; 20 } 21 } 22 int main(void) { 23 init(); 24 return 0 ; 25 }
剩下的就是考虑一下边界，比如当 i 或者 j 等于1的时候，显然都是只有一种拆分情况。
做法二：
借用hdu1284这道题的方法，也可以做这道题目，因为n的范围是120嘛,两个算法的复杂度都是O(n^2)的，当然可以了。只需要把hdu1284的代码里面把3改成n，这题就过了……
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 const int MAX = 32768+10; 5 long long d[MAX]; 6 void solve() { 7 int n, i, j; 8 while (~scanf("%d", &n)) { 9 memset(d, 0, sizeof(d)); 10 d[0] = 1; 11 for (i = 1; i <= n; ++i) { 12 for (j = i; j <= n; ++j) { 13 d[j] += d[j-i]; 14 } 15 } 16 printf("%lld\n", d[n]); 17 } 18 } 19 int main(void) { 20 solve(); 21 return 0; 22 }
优化到了一维数组，这个方法碉堡了……
参考博客：http://www.cnblogs.com/qiufeihai/archive/2012/09/11/2680840.html 膜拜……