解题思路

• 本题是典型的完全背包-组合数问题。每种硬币可无限使用，且“顺序不同视为同一种组合”，因此应当按**先枚举硬币、再枚举金额（升序）**的方式转移，避免将同一组合按排列重复计数。
• 设 dp[s] 表示凑成金额 s 的组合数。初始化 dp[0]=1（凑成 0 元有 1 种“什么都不选”的方式）。
• 转移：对每个硬币面额 c，对 s 从 c 到 amount，执行 dp[s] += dp[s - c]。最终答案为 dp[amount]。
• 当 amount=0 时，答案为 1；若无法凑出，则 dp[amount] 自然为 0。

复杂度分析

• 时间复杂度：O(N * amount)，其中 N 为硬币种类数。
• 空间复杂度：O(amount)，使用一维滚动数组。

代码实现

Python

# 题意：统计用给定硬币面额（无限个）凑成目标金额的组合数（顺序无关）
import sys

def count_ways(coins, amount):
    # dp[s]：凑成金额 s 的组合数
    dp = [0] * (amount + 1)
    dp[0] = 1  # 凑成 0 元只有 1 种方式：不选任何硬币
    for c in coins:                  # 先枚举硬币，保证不计排列
        for s in range(c, amount + 1):
            dp[s] += dp[s - c]       # 使用当前硬币 c 的转移
    return dp[amount]

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    N, amount = data[0], data[1]
    coins = data[2:2 + N]
    print(count_ways(coins, amount))

if __name__ == "__main__":
    main()

Java

// 题意：统计用给定硬币面额（无限个）凑成目标金额的组合数（顺序无关）
import java.util.*;

public class Main {
    // 计算组合数，使用完全背包的一维 DP
    static long countWays(int[] coins, int amount) {
        long[] dp = new long[amount + 1];
        dp[0] = 1; // 凑成 0 元只有 1 种方式
        for (int c : coins) {              // 先枚举硬币，避免计入排列
            for (int s = c; s <= amount; s++) {
                dp[s] += dp[s - c];        // 使用当前硬币 c 的转移
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        // 默认数据量不大，使用 Scanner 即可
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNextInt()) { sc.close(); return; }
        int N = sc.nextInt();
        int amount = sc.nextInt();
        int[] coins = new int[N];
        for (int i = 0; i < N; i++) coins[i] = sc.nextInt();
        System.out.println(countWays(coins, amount));
        sc.close();
    }
}

C++

// 题意：统计用给定硬币面额（无限个）凑成目标金额的组合数（顺序无关）
#include <iostream>
#include <vector>
using namespace std;

// 使用完全背包的一维 DP：先枚举硬币，再枚举金额（升序）
long long countWays(const vector<int>& coins, int amount) {
    vector<long long> dp(amount + 1, 0);
    dp[0] = 1; // 凑成 0 元只有 1 种方式：不选硬币
    for (int c : coins) {                 // 固定硬币，避免排列重复计数
        for (int s = c; s <= amount; ++s) {
            dp[s] += dp[s - c];           // 使用当前硬币 c 的转移
        }
    }
    return dp[amount];
}

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

    int N, amount;
    if (!(cin >> N >> amount)) return 0;
    vector<int> coins(N);
    for (int i = 0; i < N; ++i) cin >> coins[i];

    cout << countWays(coins, amount) << "\n";
    return 0;
}

Leetcode 518.零钱兑换II-原题链接

题面描述

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。 请计算并返回可以凑成总金额的硬币组合数（顺序不同视为同一种组合）。如果任意硬币组合都无法凑出总金额，返回 0。 假设每种面额的硬币都有无限个。题目数据保证结果符合 64 位带符号整数。

输入格式

• 第一行两个整数 N, amount，分别表示硬币种类数和总金额。
• 第二行包含 N 个互不相同的正整数，表示 coins[i] 的面额。

输出格式

输出一个整数，表示能够凑成总金额的组合数。

数据范围

• $1 \le N \le 300$
• $1 \le \text{coins}[i] \le 5000$，且两两不同
• $0 \le \text{amount} \le 5000$

输入样例

3 5
1 2 5

输出样例

4