HDU 1284 钱币兑换：完全背包方案数 + 数学公式 O(1) 解法

题目大意

面值 1,2,3 的硬币无限供给，兑换金额 N（N<32768），求方案数（模 20123 不需要，原题直接输出）。

完全背包 DP

#include 
#include 
#define MAX 35000
int dp[MAX];

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        memset(dp, 0, sizeof(int)*(n+10));
        dp[0] = 1;
        for (int c = 1; c <= 3; ++c)
            for (int j = c; j <= n; ++j)
                dp[j] += dp[j-c];
        printf("%d\n", dp[n]);
    }
    return 0;
}

数学公式 O(1) 解法（神代码）

枚举 3 元硬币个数 i = 0..N/3，剩余金额用 1,2 兑换，方案数为 (N-3i)/2 + 1。
总和：Σ_{i=0}^{N/3} (⌊(N-3i)/2⌋ + 1)

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        int t = n/3 + 1, sum = 0;
        for (int i = 0; i < t; ++i)
            sum += (n - 3*i)/2 + 1;
        printf("%d\n", sum);
    }
    return 0;
}

推导说明

1. 固定 3 元硬币个数 i
2. 剩余 N-3i 用 1,2 兑换：2 元硬币可取 0..⌊(N-3i)/2⌋，共 ⌊(N-3i)/2⌋+1 种
3. 累加即得

复杂度对比

• DP：O(N) 时间，O(N) 空间
• 公式：O(N/3) 时间，O(1) 空间
• 若 N 极大（如 10^9），公式可进一步求和为 O(1) 闭式