解题思路

把问题看成把正整数 $n$ 划分成若干个正整数的有序序列。设 dp[s] 表示“按顺序凑成和为 s 的方案数”。最后一枚硬币面额取 x (1 ≤ x ≤ s)，前面部分就必须凑成 s-x，于是有转移：

边界为 dp[0] = 1（和为 0 的空序列仅 1 种）。依次从小到大计算 s = 1..n 即可。

复杂度分析

• 时间复杂度：外层枚举 s=1..n，内层枚举最后一枚 x=1..s，总计 $O(n^2)$。
• 空间复杂度：仅用一维数组 dp[0..n]，为 $O(n)$。

代码实现

Python

# 功能函数：返回按顺序凑成 n 的方案数
def count_compositions(n: int) -> int:
    # dp[s]：按顺序凑成和 s 的方案数
    dp = [0] * (n + 1)
    dp[0] = 1  # 边界：空序列
    for s in range(1, n + 1):
        total = 0
        # 枚举最后一枚硬币面额 x
        for x in range(1, s + 1):
            total += dp[s - x]
        dp[s] = total
    return dp[n]

if __name__ == "__main__":
    # ACM 风格：标准输入读取一个整数
    import sys
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    print(count_compositions(n))

Java

import java.util.Scanner;

public class Main {
    // 功能函数：返回按顺序凑成 n 的方案数
    static long countCompositions(int n) {
        long[] dp = new long[n + 1];
        dp[0] = 1L; // 边界：空序列
        for (int s = 1; s <= n; s++) {
            long total = 0L;
            // 枚举最后一枚硬币面额 x
            for (int x = 1; x <= s; x++) {
                total += dp[s - x];
            }
            dp[s] = total;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        // ACM 风格输入输出：读取一个整数 n
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();
        long ans = countCompositions(n);
        System.out.println(ans);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 功能函数：返回按顺序凑成 n 的方案数
unsigned long long count_compositions(int n) {
    vector<unsigned long long> dp(n + 1, 0ULL);
    dp[0] = 1ULL; // 边界：空序列

    for (int s = 1; s <= n; ++s) {
        unsigned long long total = 0ULL;
        // 枚举最后一枚硬币面额 x
        for (int x = 1; x <= s; ++x) {
            total += dp[s - x];
        }
        dp[s] = total;
    }
    return dp[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    cout << count_compositions(n) << "\n";
    return 0;
}

题面描述

给定一个正整数 $n$。你拥有面额为 $1,2,3,\ldots,10^9$ 的硬币，每种面额的硬币数量都无限。求有多少种方式使所选硬币的总面额恰好为 $n$。 注意： 选择的顺序不同视为不同方案（例如 $2,1$ 与 $1,2$ 记为两种）。

输入输出

输入： 一行一个整数 $n$。

输出： 一行输出一个整数，表示组成面额 $n$ 的方案数。

数据范围

• $1 \le n \le 63$

样例

输入

2

输出

2

说明 可行方案：1,1；2。

输入

3

输出

4

说明 可行方案：1,1,1；2,1；1,2；3。