您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C 語言動態規劃經典：2 的冪次分拆整數（USACO 3.3 / 諾伊曼數列）

編輯：關於C

問題描述

將正整數 N (1 ≤ N ≤ 1,000,000) 分拆為若干個 2 的冪次 之和（允許重複），求分拆方案數，輸出最後 9 位。

例：N=7 有 6 種：

1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+2+2
1+1+1+4
1+2+2+2
1+2+4

方法一：遞推公式 O(N) —— 推薦

設 dp[n] 為方案數。

n 為奇數：必含至少一個 1，去掉兩個 1 等價於 n-2 → dp[n] = dp[n-1]（因 dp[n-1]=dp[n-2]）
n 為偶數：分「含 1」與「不含 1」
- 含 1：至少兩個 1 → dp[n-2]
- 不含 1：所有加數乘 2 → 等價 n/2 的分拆 → dp[n/2]

遞推：

dp[1] = 1; dp[2] = 2;
for i = 3..N:
    if i % 2 == 1: dp[i] = dp[i-1];
    else: dp[i] = (dp[i-2] + dp[i/2]) % MOD;

方法二：完全背包 DP O(N log N) —— 通用思路

物品 = 1, 2, 4, 8, ... 2^k ≤ N，每種無限件，求裝滿 N 的方案數。

dp[0] = 1;
for k = 0..24:           // 2^24 = 16,777,216 > 1e6
    coin = 1 << k;
    for i = coin..N:
        dp[i] = (dp[i] + dp[i-coin]) % MOD;

完整代碼（雙版本）

#include 
#include 
#include 

#define MOD 1000000000
#define MAXN 1000000

int64_t dp1[MAXN+1];
int64_t dp2[MAXN+1];
int coins[25];

int main() {
    /* 預計算 2 的冪 */
    coins[0] = 1;
    for (int i = 1; i < 25; i++) coins[i] = coins[i-1] << 1;

    /* 方法一：遞推 */
    dp1[1] = 1; dp1[2] = 2;
    for (int i = 3; i <= MAXN; i++) {
        if (i & 1) dp1[i] = dp1[i-1];
        else dp1[i] = (dp1[i-2] + dp1[i>>1]) % MOD;
    }

    /* 方法二：完全背包 */
    memset(dp2, 0, sizeof(dp2));
    dp2[0] = 1;
    for (int k = 0; k < 25; k++) {
        int c = coins[k];
        if (c > MAXN) break;
        for (int i = c; i <= MAXN; i++)
            dp2[i] = (dp2[i] + dp2[i-c]) % MOD;
    }

    /* 驗證一致性 */
    for (int i = 1; i <= 100; i++)
        if (dp1[i] != dp2[i]) printf("Mismatch at %d\n", i);

    /* 查詢 */
    int n;
    while (scanf("%d", &n) == 1)
        printf("%lld\n", dp1[n]);
    return 0;
}