题解 | #拼凑面额#

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    // 可用的面额
    int coins[6] = {1, 5, 10, 20, 50, 100};
    
    while (cin >> n) {
        // 创建dp数组并初始化
        vector<long> dp(n + 1, 0);
        dp[0] = 1;  // 金额为0的组合数为1
        
        // 对每种面额进行处理
        for (int i = 0; i < 6; i++) {
            // 从coins[i]开始，避免负数索引
            for (int j = coins[i]; j <= n; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        
        cout << dp[n] << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 可用的面额
        int[] coins = {1, 5, 10, 20, 50, 100};
        
        while (sc.hasNext()) {
            int n = sc.nextInt();
            // 创建dp数组并初始化
            long[] dp = new long[n + 1];
            dp[0] = 1;  // 金额为0的组合数为1
            
            // 对每种面额进行处理
            for (int coin : coins) {
                // 从coin开始，避免负数索引
                for (int j = coin; j <= n; j++) {
                    dp[j] += dp[j - coin];
                }
            }
            
            System.out.println(dp[n]);
        }
    }
}

def count_combinations(n: int) -> int:
    # 可用的面额
    coins = [1, 5, 10, 20, 50, 100]
    
    # 创建dp数组并初始化
    dp = [0] * (n + 1)
    dp[0] = 1  # 金额为0的组合数为1
    
    # 对每种面额进行处理
    for coin in coins:
        # 从coin开始，避免负数索引
        for j in range(coin, n + 1):
            dp[j] += dp[j - coin]
    
    return dp[n]

# 处理输入
while True:
    try:
        n = int(input())
        print(count_combinations(n))
    except EOFError:
        break