整数划分问题的代码实现及不同划分计数

整数划分问题是一个经典的组合优化问题，给定一个正整数 \( n \)，目标是找到所有可能的非递减整数序列之和等于 \( n \) 的不同组合方式。这个问题在计算机科学中通常涉及动态规划的方法来解决，因为寻找所有划分的数量是一个典型的子集问题，可以通过填充一个二维数组来追踪每个整数到某个目标值的划分数量。 题目中规定了时间限制（Time Limit: 1000MS）和内存限制（Memory Limit: 65536K），表明这是一个相对高效的算法实现需求，适合在标准竞赛环境中运行。总提交次数为359次，接受次数为179次，这显示该问题有一定的挑战性，但并非无法解决。 代码片段展示了如何使用动态规划方法来计算整数划分的个数。主要的函数 `Calc()` 通过一个 \( 121 \times 121 \) 的二维数组 `p[i][j]` 来存储从1到 \( i \) 的整数中，有多少种方式可以得到和为 \( j \) 的划分。初始化时，设置边界条件：当 \( i \) 或 \( j \) 为1时，有1种划分；当 \( i < j \) 或者 \( i = j \) 时，根据定义进行相应的递推。 在 `main()` 函数中，首先调用 `Calc()` 函数计算数组，然后读取用户输入的测试用例数量 \( t \)，对于每一个测试用例 \( n \)，输出对应的划分个数，即 `p[n][n]`。 这个算法的关键在于利用了状态转移方程：如果 \( i \) 小于 \( j \)，那么没有从 \( i \) 到 \( j \) 的划分；如果 \( i \) 等于 \( j \)，则只有一种选择（自己本身）；如果 \( i > j \)，则可以从 \( i \) 的前一个数 \( i - 1 \) 和剩余部分 \( i - j \) 的划分组合而成。 总结来说，整数划分问题是一个典型的动态规划问题，通过数组 `p` 存储并递归地计算不同整数和的划分个数，这种方法避免了暴力枚举，显著提高了计算效率。理解并掌握动态规划在这类问题中的应用是提高编程技能的关键。