HDU 1028 解題報告：整數拆分數計數（完全背包視角）
求將整數 n (≤ 120) 拆分為若干正整數之和的方案數（順序無關，即分區數 p(n)）。多測試用例，直到 EOF。
完全背包模型
物品：整數 1, 2, ..., n，每種無限件，價值均為 1，背包容量 n。求裝滿背包的方案數。
dp[v]：湊出和 v 的方案數。
初始 dp[0] = 1。
狀態轉移：for i=1..n: for v=i..n: dp[v] += dp[v-i]（正序循環，完全背包）。
代碼實現
#include
#include
#define MAXN 125
long long dp[MAXN];
int main() {
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for(int i=1; i
關鍵點
- 預計算：
MAXN=125 覆蓋所有可能 n，一次 DP 答所有查詢。
- long long：
p(120) ≈ 2.6e8，32 位有符號整數上限 2.1e9 勉強夠，但建議用 64 位防溢出擴展。
- 順序無關：外層循環遍歷「物品（加數）」，內層正序遍歷「容量（和）」保證組合不重複計數（
1+2 與 2+1 視為同一方案）。
數學背景
這是經典的分區函數 p(n)。歐拉五邊形數定理可在 O(n√n) 計算，但 n=120 完全背包 O(n^2) 極簡且足夠快。
