整数拆分方案计数 - C/C++/Java 实现 - 常规

"给定一个整数 n，将其无序拆分成最大数为 k 的拆分数，（n,k 不超出 100）\n要求：所有的拆分方案不重复。\n如当 n=4,k=4 时，一共有 5 种拆分方案，拆分如下：\n\n(1)4=1+1+1+1\n(2)4=1+1+2\n(3)4=1+3\n(4)4=2+2\n(5)4=4\n输入格式:\n每一行输入一组整数 n,k，遇到键盘结束符^Z 或文件结束符 EOF 时结束输入。\n\n输出格式:\n按行输出每组的拆分方案数。\n\n输入样例:\n4,4\n5,4\n输出样例:\n5\n6\n代码长度限制\n16 KB\n时间限制\n400 ms\n内存限制\n64 MB\n用 c/c++/java 实现内容：#include \n#include \nusing namespace std;\n\nvector<vector> dp(101, vector(101, 0));\n\nint partition(int n, int k) {\n if (n == 0 || k == 1) {\n return 1;\n }\n if (n < k) {\n return partition(n, n);\n }\n if (dp[n][k] != 0) {\n return dp[n][k];\n }\n dp[n][k] = partition(n - k, k) + partition(n, k - 1);\n return dp[n][k];\n}\n\nint main() {\n int n, k;\n while (cin >> n >> k) {\n cout << partition(n, k) << endl;\n }\n return 0;\n}\n"